The problem is to count the number of inversions in an array. Two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j.
For example, the sequence 1, 20, 6, 4, 5 has five inversions (20, 6), (20, 4), (20, 5), (6, 4) and (6, 5).
We can modify the mergesort algorithm to count the number of inversions while sorting. This takes time O(nlogn) for an array of size n.
The algorithm belongs to the class of divide-and-conquer algorithms and has the following steps:
- Divide: Divide the array of size n into two subarrays of size n/2 each.
- Conquer: Recursively compute the number of inversions in both subarrays.
- Combine: Count the number of inversions split across the two subarrays. This can be done in linear time by modifying the merge procedure of mergesort such that when it copies an element from the right subarray to the original array, it adds the number of remaining elements in the left subarray to the count of split inversions.
Take a look at the C++ implementation.
Try your hand at problem INVCNT, which uses this idea.