Count Inversions

An inversion is a pair i < j with a[i] > a[j]: an out-of-order pair. Piggyback on merge sort: while merging two sorted halves, every time you pull from the right half, it jumps ahead of all remaining left elements.

Concept

Count during the merge

Split, recurse, then merge two sorted halves. When the right element is smaller than the current left element, it's smaller than every remaining left element too, so add (mid - i + 1) inversions at once.

Three sources sum up

Inversions fully inside the left half
Inversions fully inside the right half
Cross inversions counted at merge time
Total = left + right + cross

Interactive

Merge and tally

Left half Right half Inversion counted Merged output

Array

merged:

slowfast

Step 0

Total inversions

This merge

Merges done

Range

–

Implementation

C++

long long mergeCount(vector<int>& a, int lo, int mid, int hi) {
    vector<int> tmp; tmp.reserve(hi - lo + 1);
    int i = lo, j = mid + 1;
    long long inv = 0;
    while (i <= mid && j <= hi) {
        if (a[i] <= a[j]) tmp.push_back(a[i++]);
        else {
            tmp.push_back(a[j++]);
            inv += (mid - i + 1);   // a[i..mid] all > a[j]
        }
    }
    while (i <= mid) tmp.push_back(a[i++]);
    while (j <= hi)  tmp.push_back(a[j++]);
    for (int k = 0; k < tmp.size(); k++) a[lo + k] = tmp[k];
    return inv;
}

long long countInv(vector<int>& a, int lo, int hi) {
    if (lo >= hi) return 0;
    int mid = (lo + hi) / 2;
    return countInv(a, lo, mid)          // left
         + countInv(a, mid + 1, hi)      // right
         + mergeCount(a, lo, mid, hi);   // cross
}

Complexity

Time

O(n log n)

Merge sort's recursion tree: log n levels, O(n) work per level.

Space

O(n)

The temporary buffer used during each merge.

Brute force

O(n²)

Checking all pairs. The merge trick is the big win.

Notes

The key line: inv += mid - i + 1. Because both halves are sorted, one right-element beating a[i] beats everything from i to mid in one shot.
Use a[i] <= a[j] (not <) so equal elements aren't miscounted as inversions.
Watch overflow: the max inversion count is n(n-1)/2, use 64-bit.
This is the canonical "merge sort pattern", count-of-smaller-after-self and reverse-pairs (LC 493) are variations of the same merge.
A BIT / Fenwick tree solves it too, but the merge approach needs no extra structure.