Counting Inversions

An inversion is a pair of positions that are out of order: an earlier element bigger than a later one. Counting them measures how unsorted an array is. It is also the number of swaps bubble sort would make, and the standard measure of how differently two people ranked the same list.

Counting them pair by pair is O(n²). The fast way is to notice that merge sort already compares elements across its two halves — and at the moment it takes an element from the right half, it has learned how many left-half elements are bigger. That knowledge is free; you only have to count it.

The problem

Given an array of integers, count the pairs of indices (i, j) with i < j and nums[i] > nums[j].

• [2, 5, 8, 1, 3, 7] → 6. The pairs are (2, 1), (5, 1), (8, 1), (5, 3), (8, 3) and (8, 7).
• [1, 2, 3] → 0. A sorted array has no inversions. [3, 2, 1] → 3, the most three elements can have.

Constraints: 1 ≤ n ≤ 10⁵, values fit in 32 bits, duplicates allowed.

Clarifying questions

• Do equal values count? No — the condition is strictly greater.
• Return the count or the pairs? The count. (Listing the pairs can take n²/2 lines, so no algorithm can beat O(n²) for that.)
• Can the answer be large? Up to n(n − 1)/2, about 5 × 10⁹ for n = 10⁵. Python integers are fine; in Java or C++ use a 64-bit type.
• May I modify the input? Prefer not; the solution below works on copies.

Approach 1: the simple way

Check every pair.

def count_inversions_brute(nums: list[int]) -> int:    n = len(nums)    return sum(1 for i in range(n) for j in range(i + 1, n) if nums[i] > nums[j])

It is O(n²) time and O(1) space. For n = 10⁵ that is about 5 × 10⁹ comparisons. Measured, 5,000 elements took half a second in Python, so 10⁵ would take several minutes.

The key insight

Split the array into a left half and a right half. Every inversion is one of three kinds: both elements in the left half, both in the right half, or one in each — a cross inversion. The first two kinds are the same problem on a smaller array, so recursion handles them. The cross kind is where the saving is.

For cross inversions, the order inside each half does not matter — only which half an element came from. So you may sort each half first. Now merge them, as merge sort does. Whenever the smallest remaining element is on the right (right[j] < left[i]), it is smaller than left[i] and therefore smaller than every remaining left element, because the left half is sorted. Each of those forms a cross inversion with right[j]. That is len(left) − i inversions counted in one step, without looking at them one by one.

So "sort and count" returns two things: the sorted array, and its inversion count. The count is left count + right count + cross count.

Approach 2: optimised — count during merge sort

1def count_inversions(nums: list[int]) -> int:2    """Pairs i < j with nums[i] > nums[j], counted during a merge sort."""3    def sort_count(arr: list[int]) -> tuple[list[int], int]:4        if len(arr) <= 1:5            return arr, 06        mid = len(arr) // 27        left, a = sort_count(arr[:mid])8        right, b = sort_count(arr[mid:])9        merged, cross, i, j = [], 0, 0, 010        while i < len(left) and j < len(right):11            if left[i] <= right[j]:12                merged.append(left[i])13                i += 114            else:15                merged.append(right[j])16                j += 117                cross += len(left) - i     # right[j] is smaller than all of left[i:]18        merged.extend(left[i:])19        merged.extend(right[j:])20        return merged, a + b + cross2122    return sort_count(nums)[1]

It is the merge sort template with one added line. The <= matters twice: it keeps the sort stable, and it makes sure an equal pair is not counted as an inversion.

Dry run on [2, 5, 8, 1, 3, 7]. Each half, [2, 5, 8] and [1, 3, 7], is already sorted with 0 inversions inside. The top-level merge:

The right half is used up; [8] is copied. Total 0 + 0 + 6 = 6, matching the six pairs listed in the problem.

Complexity: O(n log n) time — the same as merge sort, since the counting adds O(1) per merge step. O(n) space for the halves and merged lists (plus O(log n) recursion depth). Measured on 10⁵ random values, it took about 0.2 seconds.

Approach 3: a Fenwick tree, named

Walk left to right, and for each value ask "how many values seen so far are larger?" A Fenwick tree (binary indexed tree) over the values' ranks answers that and records the new value in O(log n) each, for O(n log n) total. It needs coordinate compression first — replacing values by their rank — because values can be up to 2³¹. Name it as the alternative; the merge version needs no extra data structure and is easier to get right in an interview. (A Fenwick version was also tested against the brute force.)

Edge cases

• Empty or one element: 0.
• Sorted: 0 — every merge takes from the left first.
• Reverse sorted: n(n − 1)/2, the maximum.
• All equal, [4, 4, 4]: 0, because the merge takes from the left on ties.

Follow-ups

• Reverse pairs — count i < j with nums[i] > 2 × nums[j]? The condition is no longer the merge's own comparison, so count in a separate two-pointer pass over the two sorted halves before merging. Still O(n log n).
• For each element, how many smaller elements are to its right? Same merge, but credit the count to individual elements — the next lesson, Count of Smaller Numbers After Self.
• Minimum adjacent swaps to sort the array? Exactly the inversion count: each adjacent swap fixes exactly one inversion.