Counting inversions

SORT-2 counted inversions while merge sort ran. This lesson looks at why that count is right, and then uses the same idea for three new questions: a count for every value, pairs with a different rule, and a distance between two rankings. The combine step does all the work, and it costs only O(n).

Counting while merging, again

An inversion is a pair of positions i < j with a[i] > a[j]: a bigger value before a smaller one (SORT-1). A sorted list has none, and a reversed list of n values has all n(n − 1)/2 pairs. Checking every pair costs O(n²).

Split the list in half. Every inversion has both values in the left half, or both in the right half, or one in each. Recursion counts the first two kinds. For the third kind the order inside each half no longer matters, because every left value still comes before every right value. So each half may be sorted first, and then one merge counts the pairs. Step through “Whole sort”.

Why exactly once: two positions are in the same part at the top and in different parts at the bottom. Going down the tree, there is exactly one call where they are split apart, and only that call’s merge sees them as a left value and a right value. So no inversion is missed and none is counted twice. The cost is merge sort’s: T(n) = 2 T(n/2) + O(n), which is O(n log n).

Equal values are not inversions. On a tie, take the left value first; then a right value equal to a left one is never counted as smaller.

A count for every value

A harder question: for each position, how many smaller values come after it? For [5, 2, 6, 1] the answer is [2, 1, 1, 0]. The total of these counts is the number of inversions, but now each value needs its own count.

Look at the merge from the left value’s side, as “One merge” does. When a left value is placed, the right values placed before it are exactly the right values smaller than it, and they all came after it in the list. So add j, the number of right values taken so far, to that value’s count. SORT-2 added the count at the other moment: when a right value is placed, it is smaller than every left value still waiting. Both moments give the same total, but only the first gives each value its own count.

One more detail. Merge sort moves values around, so a count must stay with its value. Sort a list of positions instead of the values, comparing a[p] for positions p, and keep the counts in a list indexed by the original position. Practice problem 3 asks for this.

A different rule for pairs

Count the pairs i < j with a[i] > 2 × a[j]. The split still works: count inside each half, then the pairs that cross. But the merge can no longer count them as it goes, because the merge order follows a[i] > a[j], not a[i] > 2 × a[j]. Count them in a separate pass first, while both halves are sorted:

def cross_pairs(left, right):
    """Pairs (x in left, y in right) with x > 2 * y; both lists sorted."""
    count = 0
    j = 0
    for x in left:                     # x only grows, so j only moves right
        while j < len(right) and x > 2 * right[j]:
            j += 1
        count += j                     # right[0..j-1] all fit with x
    return count

j never moves back, so the pass costs O(n), and the whole method stays at O(n log n). This is the general shape: when the counting rule and the sorting rule differ, count with a two-pointer walk over the sorted halves, then merge.

Comparing two rankings

Two judges rank the same 5 trains by punctuality. How different are their rankings? Count the pairs of trains that the judges put in opposite orders. This number is the Kendall tau distance. It is 0 when the rankings agree and n(n − 1)/2 when one is the reverse of the other.

To compute it, rename the trains by their place in the first judge’s list (the first train becomes 0, the second 1, and so on), write the second judge’s list with the new names, and count its inversions. A pair in opposite orders is exactly an inversion of that list. Search engines and recommender systems compare rankings this way, and the same count measures how far a list is from sorted: insertion sort makes exactly one move per inversion (SORT-1).

Another way: a Fenwick tree

RNGQ-3 counted inversions with a Fenwick tree. Read the list from right to left, and keep a count of how many times each value has been seen so far. For each value, the number of smaller values already seen is a prefix sum over the counts: exactly the smaller values to its right. Then record the value. Each step is O(log n).

Values can be large or negative, so first replace each value by its rank among the distinct values (0 for the smallest, 1 for the next, and so on). This step is called coordinate compression and costs one sort. Both methods are O(n log n). The merge method needs no compression and works with any values that can be compared; the Fenwick method also answers questions while values keep arriving.