Let A be an array of n distinct numbers. If iA[j], then the pair (i, j) is called an inversion.
Devise an ?(n lg n) worst-case time algorithm for determining the number of inversions in A. Implement your algorithm and prove that it has needed complexity.