The Number of Inversions in an Array

Problem:
Let \(A[1...n]\) be an array of \(n\) distinct numbers. If \(i \lt j\) and \(A[i] \gt A[j]\), then the pair \( (i,j) \) is called an inversion of A. Determine the number of inversions given an array of distinct numbers.

Solution 1:
Naive approach. There are \( \frac{n(n-1)}{2} \) number pairs in an array of size \(n\), and check one by one. The time complexity is \(O(n^2)\).

We can have a better solution for this problem, which is proposed as below.

Solution 2:
Divide-and-conquer. This strategy works in similar way to merge-sort, and bears time complexity \(n\log n\).