Merge Sort and Counting Inversions

Merge sort recursively splits an array in half, sorts each half, and merges them back together in order. That merge step — walking two sorted halves and interleaving them — happens to do something extra for free: every time it takes an element from the right half before it's finished taking elements from the left half, that's a pair of numbers that appears out of order relative to a fully sorted array. Counting those moments as they happen counts every inversion in the array, in the same $O(n \log n)$ time the sort already costs.

The idea: an inversion is a pair in the wrong relative order

An inversion is any pair of positions $i < j$ where $a[i] > a[j]$ — a bigger number sitting before a smaller one. A fully sorted array has zero inversions; a fully reversed array has the maximum, $\binom{n}{2}$. Counting inversions naively means checking every pair, $O(n^2)$. Merge sort's merge step already compares elements from the left and right halves in order — you get the count almost as a side effect.

During the merge of two already-sorted halves left and right: whenever you take an element from right because it's smaller than the current element in left, every remaining element in left also forms an inversion with it (since left is sorted, they're all bigger too). Add the count of remaining left elements to the running total right there.

Worked example: [2, 4, 1, 3, 5]

Split into [2, 4] and [1, 3, 5], sort each recursively (no inversions found yet within a single split of size ≤ 2 that's already ordered), then merge:

• Compare 2 (left) vs 1 (right): 1 is smaller, take it. Left still has [2, 4] = 2 elements remaining → add 2 inversions (2>1, 4>1).
• Compare 2 vs 3: 2 smaller, take it, no inversion (left element taken).
• Compare 4 vs 3: 3 smaller, take it. Left still has [4] = 1 element remaining → add 1 inversion (4>3).
• Compare 4 vs 5: 4 smaller, take it.
• Right exhausted, append remaining 5.

Total: 2 + 1 = 3 inversions. Verify by brute force: pairs out of order in [2,4,1,3,5] are (2,1), (4,1), (4,3) — exactly 3.

def sort_and_count(arr):                     # returns (sorted_array, inversion_count)
    if len(arr) <= 1:
        return arr, 0
    mid = len(arr) // 2
    left, inv_l = sort_and_count(arr[:mid])
    right, inv_r = sort_and_count(arr[mid:])

    merged, i, j, inv_split = [], 0, 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
            inv_split += len(left) - i        # every remaining left element inverts with right[j]
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged, inv_l + inv_r + inv_split

Where it shows up

Interviewers pose this directly as "count inversions" or dress it up as "minimum adjacent swaps to sort an array" (the swap count equals the inversion count) — recognizing the merge-sort connection is the difference between an $O(n^2)$ and $O(n \log n)$ solution. In quant work, inversion counts measure how different two rankings are — how much a ranked list of names by momentum signal disagrees with a ranked list by value signal, which is the combinatorial idea underlying rank correlation measures like Kendall's tau; see Spearman and Kendall Rank Correlation for the related rank-based statistic used more often in practice.