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$.