Counting Inversions in an Array using Merge Sort

Counting inversions is a classic application of the principle that divide and conquer can gather extra information during its combine step at no asymptotic cost. The merge step of merge sort compares elements — by counting how many left-array elements each right-array element 'jumps over', you get the inversion count for free.

This pattern — extracting additional information during a standard D&C operation — appears throughout algorithm design. Counting inversions for collaborative filtering, computing closest pair distance during a geometric divide, finding maximum subarray during merge. The lesson is: when you already have a D&C structure, ask what else you can compute in the combine step.

What is an Inversion?

A pair (i, j) is an inversion if i < j but arr[i] > arr[j].

Example: arr = [2, 4, 1, 3, 5] Inversions: (2,1), (4,1), (4,3) → count = 3

Applications: - Measuring how similar two preference rankings are - Minimum swaps to sort an array = number of inversions - Kendall tau distance between two permutations

Modified Merge Sort

During the merge step of merge sort, when we pick an element from the right subarray before exhausting the left subarray, every remaining element in the left subarray forms an inversion with it.

def count_inversions(arr: list) -> tuple[list, int]:
    """Returns (sorted_array, inversion_count)"""
    if len(arr) <= 1:
        return arr, 0
    mid = len(arr) // 2
    left,  left_inv  = count_inversions(arr[:mid])
    right, right_inv = count_inversions(arr[mid:])
    merged, split_inv = merge_count(left, right)
    return merged, left_inv + right_inv + split_inv

def merge_count(left: list, right: list) -> tuple[list, int]:
    merged, inversions = [], 0
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            # left[i..] all form inversions with right[j]
            inversions += len(left) - i
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged, inversions

_, count = count_inversions([2, 4, 1, 3, 5])
print(f'Inversions: {count}')  # 3

_, count = count_inversions([5, 4, 3, 2, 1])
print(f'Inversions in reverse: {count}')  # 10

Why This Works

When merging two sorted halves, any element right[j] that is taken before left[i] forms inversions with all of left[i..end]. This is because: 1. left is sorted → all remaining elements left[i..] are ≥ left[i] > right[j] 2. All these elements come before right[j] in the original array (they're in the left half)

So inversions += len(left) - i counts them all in O(1).

Application — Minimum Swaps to Sort

The minimum number of adjacent swaps needed to sort an array equals the number of inversions. Each adjacent swap reduces the inversion count by exactly 1.

def min_swaps_to_sort(arr):
    _, count = count_inversions(arr)
    return count

print(min_swaps_to_sort([3, 1, 2]))  # 2 swaps: [3,1,2]→[1,3,2]→[1,2,3]

Frequently Asked Questions