Section 5.3 Counting Inversions

The motivation for this type of problem is based in the analysis of a set of rankings compared to a different set of rankings of the same items. A way to compare these sets of ordered items is to look at how many pairs are “out of order” from one ranking to another. An inversion occurs when indices i<j but a_i>a_j.

Looking at every pair of numbers would require O(n²)time, so to find the O(n log n) solution, we must find one that does not even have to evaluate every value. This solution is to divide the list of numbers into two half-sized sublists then counting the number of inversions in each half and finally counting inversions between the two halves. The merge-and-count algorithm is the solution that hinges on this principle.

Merge-and-count works by maintaining pointers to the front of each sublist and removing the lesser one from its sublist when it is added to what will become the sorted list. The algorithm must also count the number of inversions in addition to ordering the list. It does this by increasing the count of inversions by whatever the remaining size of the first subset of rankings is. This operation counts a possibly large number of inversions in constant time. Thus, O(n log n) running time.

I found this chapter fairly straightforward to understand.