counting inversions

Two friends each rank the same ten movies. How different are their tastes? One natural measure counts the pairs of movies they disagree about: pairs where friend A ranks movie X above Y but friend B ranks Y above X. Relabel things so friend A's order is 1,2,3,...; then in friend B's list, an inversion is any pair of positions (i, j) with i < j but value at i greater than value at j — a pair that is out of order. Counting these measures how far a list is from sorted.

Checking all pairs is O(n^2). The clever observation is that counting inversions piggybacks on merge sort almost for free. Run merge sort; whenever the merge step pulls an element from the RIGHT half before some elements still remaining in the LEFT half, those remaining left elements are each larger than the one just taken yet sit before it in the original order — so each is an inversion. Concretely, when you copy a right-half element while k elements remain in the left half, add k to the inversion count. Since the two halves are individually sorted before merging, this single addition correctly tallies every cross-half inversion in O(n) per merge, and inversions entirely within a half are counted by the recursive calls. Total time T(n) = 2 T(n/2) + O(n) = O(n log n).

Counting inversions is the model example of augmenting a divide-and-conquer algorithm to compute something extra during the combine step at no asymptotic cost. It quantifies sortedness, underlies the Kendall tau distance between rankings, scores collaborative-filtering similarity, and shows up in competitive programming. The key subtlety to get right: the count must be taken at the moment of the merge and split into within-left, within-right, and crossing parts, exactly mirroring the three buckets of the maximum-subarray combine.