Count InversionsCounting inversions

01Why it exists

Reach for it when you see:Inversions, i < j but a[i] > a[j], how much two rankings disagree, Kendall tau, minimum adjacent swaps, how many to my right are smaller, the parity of a permutation, counting during a merge sort.

02The core idea

An inversion is a pair of positions with i < j and a[i] > a[j] — an earlier element that is bigger than a later one. With n elements there are at most n(n−1)/2 of them (fully reversed) and as few as 0 (already sorted), so the count measures how far the sequence is from being in order: it equals the number of swaps bubble sort makes, the number of shifts insertion sort makes, and the minimum number of adjacent swaps needed to sort the sequence. Comparing every pair with two nested loops is O(n²), which is 5 billion comparisons at n = 10⁵.

The divide-and-conquer insight: cut the array in half, and every inversion falls into one of three buckets — both elements in the left half, both in the right half, or one in each (crossing). Recursion counts the first two. A crossing inversion only asks whether some value in the left half exceeds some value in the right half, which does not depend on how either half is ordered internally, so you can sort both halves first and count afterwards — and that is precisely the merge step of a merge sort. During the merge, with a left pointer i and a right pointer j: if a[i] ≤ a[j] take the left element; otherwise take a[j] from the right, at which point the untaken left elements a[i..mid−1] are all ≥ a[i] > a[j] and all originally sat before a[j], so you add mid − i inversions at once. Every crossing inversion (left x, right y) is counted exactly once, at the moment y comes out: the left elements bigger than y have not been taken yet, and the ones that are not bigger already have.

The complexity is merge sort's own T(n) = 2T(n/2) + O(n), so O(n log n) time and O(n) scratch space, plus O(log n) recursion depth. The answer itself can reach n(n−1)/2, which overflows a 32-bit integer once n passes 65,536, so C++ needs a long long. The other O(n log n) approach uses a Fenwick tree: compress the values to ranks, scan left to right, and for each element query how many already-seen values are bigger than it before adding itself. That version never reorders the array, which suits counting as the data streams in.

Common traps: equal values are not inversions, so the merge has to be written as a[i] ≤ a[j] and take the left one first — writing < counts ties as well. The counting has to match the direction you take from: "add mid − i when taking from the right" and "add j − mid when taking from the left" are two equivalent formulations, and mixing them double-counts or misses pairs. Sorting the input array directly scrambles the caller's data. For variants, check whether the condition still lines up with the merge order: Reverse Pairs uses a[i] > 2·a[j], which does not match the order elements come out in, so it needs a separate two-pointer count before the merge; Count of Smaller Numbers After Self wants a count per element, so you sort indices rather than values. This lesson is the same code as Merge Sort with one extra counting line, and the 13 shifts in the Insertion Sort demo are an inversion count too.

03The algorithm

1. 1Define sort(lo, hi): sort [lo, hi) and return the number of inversions inside that range. Return 0 when the length is ≤ 1.
2. 2Recurse on the halves: cnt = sort(lo, mid) + sort(mid, hi), the inversions inside each half.
3. 3Merge: compare a[i] against a[j]. Take the left one when a[i] ≤ a[j]; otherwise take the right one and add cnt += mid − i.
4. 4Write the merged result back into [lo, hi) and return cnt. The outermost return value is the answer — use a 64-bit integer for it.
5. 5If you need a count per element, or the condition is not a plain greater-than (a[i] > 2·a[j], say), sort indices instead, or count separately with two pointers before merging.

04Interactive demo

Judge B's ranks for eight entries, [3, 1, 4, 7, 2, 8, 5, 6], already ordered by judge A's ranking — so the inversions are exactly the pairs of entries the two judges disagree on. The top row is the whole array, with the segment being merged in yellow; below it are the left half, the right half and the merged result, with the next two elements to compare in blue and the ones already taken in grey. Every time a right element comes out first (green in the merged result), all the left elements still waiting turn yellow and are counted as inversions in one go. The total is 8 pairs, matching the brute-force comparison, or 29% of all 28 pairs.

05Code

Python has the merge sort version, a brute-force version to check it against, and the application that turns two rankings into an inversion count to get the Kendall tau distance. C++ has the merge sort version and a Fenwick tree version, and uses 100,000 fully reversed numbers to show why the answer has to be a long long.

# Merge sort counting inversions on the side: when a right element comes out first, every left element still waiting is bigger
def count_inversions(a):
    a = a[:]                                 # sort a copy, leave the input untouched
    buf = [0] * len(a)

    def sort(lo, hi):                        # sort a[lo:hi] and return the inversions inside it
        if hi - lo <= 1:
            return 0
        mid = (lo + hi) // 2
        cnt = sort(lo, mid) + sort(mid, hi)  # inside the left half + inside the right half
        i, j = lo, mid
        for k in range(lo, hi):
            if j == hi or (i < mid and a[i] <= a[j]):
                buf[k] = a[i]                # ties are not inversions, so take the left one first
                i += 1
            else:
                buf[k] = a[j]
                j += 1
                cnt += mid - i               # across the halves: the mid - i left elements left over all beat a[j]
        a[lo:hi] = buf[lo:hi]
        return cnt

    return sort(0, len(a))


def count_inversions_brute(a):               # O(n²) version to check against
    return sum(1 for i in range(len(a)) for j in range(i + 1, len(a)) if a[i] > a[j])


# Kendall tau distance between two rankings: how many pairs the two rankings order the opposite way
def kendall_tau_distance(rank_a, rank_b):
    pos = {item: i for i, item in enumerate(rank_b)}
    return count_inversions([pos[item] for item in rank_a])   # write down B's ranks in A's order


if __name__ == "__main__":
    judge_b = [3, 1, 4, 7, 2, 8, 5, 6]                       # the same data as the demo
    print(count_inversions(judge_b), count_inversions_brute(judge_b))   # 8 8
    print(kendall_tau_distance(["A", "B", "C", "D"], ["B", "A", "D", "C"]))   # 2
    print(count_inversions(list(range(5000, 0, -1))))       # 12497500 = 5000 × 4999 / 2

06Practice

• LeetCode 775Global and Local Inversions (every inversion has to be an adjacent one)Medium
• LeetCode 1850Minimum Adjacent Swaps to Reach the Kth Smallest Number (the number of adjacent swaps is the inversion count)Medium
• LeetCode 315Count of Smaller Numbers After Self (a count per element, so sort indices)Hard
• LeetCode 493Reverse Pairs (the condition is a[i] > 2·a[j], so count with two pointers before merging)Hard
• LeetCode 327Count of Range Sum (run the same merge-and-count over prefix sums)Hard