Count Inversions

Count Inversions asks: how far is an array from being sorted? An inversion is any pair that is out of order. The clever part is that you can count them all while you sort — for free — by piggybacking on merge sort.

The slow way first

The obvious idea: check every pair. Two nested loops, and for each i < j test whether a[i] > a[j]. That is correct, but it is O(n²) — for a large array it is far too slow.

The question to ask: can I count inversions while doing work I am already doing? Sorting is exactly that work. If I sort by repeatedly merging two already-sorted halves, the merge step reveals the inversions between the halves directly.

The idea: count during the merge

Merge sort splits the array in half, sorts each half, then merges the two sorted halves back together. The trick is what happens during that merge. Walk both halves with pointers i (left) and j (right). When right[j] < left[i], the right element jumps ahead of left[i]. But the left half is sorted, so every remaining left element is also greater than right[j] — that is len(left) - i inversions, counted in a single step.

Each recursive call returns both the sorted half and its inversion count. The total is the count from the left half, plus the count from the right half, plus the cross-half inversions found while merging.

Walk through it

Step through the animation. The halves left = [2, 4] and right = [1, 3, 5] are already sorted. Pointer i walks the left, j walks the right. When 1 beats 2, both remaining left values (2 and 4) are larger, so we add 2 inversions at once. Later, 3 beats 4, adding 1 more. Taking from the left side never adds anything. Total: 3.

Pseudocode

sort_count(a):
    if a has 0 or 1 elements: return a, 0
    split a into left and right halves
    sort each half recursively, getting (sorted, count) for each
    inv = left_count + right_count
    walk both sorted halves with pointers i and j:
        if right[j] < left[i]:
            inv += (number of left elements still remaining)   # the key line
            take right[j]
        else:
            take left[i]
    append whatever remains of either half
    return merged, inv

The Python solution

def sort_count(a):
    if len(a) <= 1:
        return a, 0
    mid = len(a) // 2
    left, x = sort_count(a[:mid])
    right, y = sort_count(a[mid:])
    merged, inv = [], x + y
    i = j = 0
    while i < len(left) and j < len(right):
        if right[j] < left[i]:
            inv += len(left) - i
            merged.append(right[j])
            j += 1
        else:
            merged.append(left[i])
            i += 1
    merged += left[i:]
    merged += right[j:]
    return merged, inv

• The base case: an array of 0 or 1 elements is already sorted with 0 inversions.
• We sort each half recursively. Each call hands back (sorted_half, its_inversion_count).
• inv starts as x + y — the inversions found entirely inside each half.
• Lines 10 and 11 are the heart of it: when right[j] < left[i], every one of the len(left) - i left elements still waiting is greater than right[j], so they are all inversions.
• Taking from the left side (the else) adds nothing — the left element is smaller, so it is in order with the right.
• After the loop, one side may have leftovers; they trail along and add no further inversions.

Complexity

The structure is identical to merge sort: log n levels of recursion, each doing O(n) work across all the merges. The counting adds no extra asymptotic cost — it rides along on the comparisons we already make.

When this pattern shows up

Practice