Counting inversions

Exercise 2.11

Write an algorithm that counts the number of inversions in a table with n elements. The worst-case cost of the algorithm should be O(n \log n).

An inversion in a table A[1 \dots n] is a pair of indices that point to elements in inverted order; that is, a pair (i, j) such that 1 \leq i < j \leq n and A[i] > A[j].

Hint

As a starting point you might want to revise how the MergeSort works.

Extra

After doing this exercise, you might want to solve the Jutge problem P80595 How many inversions?