Divide-and-Conquer Counting: Inversions & Reverse Pairs

1. Introduction & Motivation

An inversion in an array is a pair of positions $i < j$ where $a[i] > a[j]$ — a pair that is "out of order" relative to a fully sorted array. Counting inversions answers a question that shows up constantly in practice: how far is this sequence from sorted? A freshly sorted array has zero inversions; a reverse-sorted array has the maximum possible number. That single number is a genuine measure of disorder, used to compare rankings, detect near-sorted data worth exploiting, and quantify similarity between two orderings of the same items.

This lesson is about a family of problems, not just one. Divide-and-conquer counting problems share a shape: you want to count something over all pairs (or triples) drawn from across the two halves of a divide-and-conquer split, and it turns out you can piggyback that count on a combine step you were already going to run. Merge sort's merge step walks through two sorted halves and decides, for every element, where it belongs relative to the other half. That is already almost all the information needed to count cross-half inversions — augmenting the merge to also accumulate a running count costs no extra asymptotic time. The same idea, pushed slightly further with an extra pass, counts reverse pairs: pairs $i < j$ where $a[i] > 2 \cdot a[j]$, a harder variant that cannot be read directly off the plain merge comparisons.

Both problems are worked out in full here: the standard merge-sort-based Inversion Count algorithm, and the Reverse Pairs variant that needs a small but crucial modification to the merge step.

2. Prerequisites

This lesson assumes you can already trace and reason about merge sort's split-recurse-merge structure. It is covered in full, including a three-language implementation, in Fundamental Sorting Algorithms — the merge procedure itself is not re-derived here, only extended.

A related but different divide-and-conquer technique is Quickselect, covered in depth in the Selection Algorithms Deep Dive section of the selection and order-statistics lesson. Quickselect also splits the input and recurses into one half, but it solves selection (find the $k$-th smallest element) rather than counting. It is worth knowing that both problems live in the same divide-and-conquer family, even though their recurrences and goals differ — Quickselect's mechanics are not repeated here.

Inversion counting itself already has a solution elsewhere on this site: the Sort-by-Threshold and Event Sorting section of the offline-queries lesson counts inversions with a left-to-right sweep over a Fenwick tree (Binary Indexed Tree), an entirely different technique built on offline sweeps rather than divide-and-conquer. That approach is not repeated here either — it is cross-linked as an alternative in Applications & Alternatives. This lesson instead develops the merge-sort-based technique in full, since it belongs to the divide-and-conquer family and has not been covered anywhere else on this site yet.

3. A Concrete Example

flowchart TD
    Root["split [5, 2, 6, 3, 1, 4]
merge result [1, 2, 3, 4, 5, 6]
contributes +7"]
    L["split [5, 2, 6]
merge result [2, 5, 6]
contributes +1"]
    R["split [3, 1, 4]
merge result [1, 3, 4]
contributes +1"]
    LL["base case [5]"]
    LR["split [2, 6]
merge result [2, 6]
contributes +0"]
    LRL["base case [2]"]
    LRR["base case [6]"]
    RL["base case [3]"]
    RR["split [1, 4]
merge result [1, 4]
contributes +0"]
    RRL["base case [1]"]
    RRR["base case [4]"]

    Root --> L
    Root --> R
    L --> LL
    L --> LR
    LR --> LRL
    LR --> LRR
    R --> RL
    R --> RR
    RR --> RRL
    RR --> RRR
                            

The tree has $\log_2 6 \approx 2.6$ (rounded up to 3) levels of splitting, and every internal node performs exactly one merge. Summing every node's contribution — $7 + 1 + 1 + 0 + 0 = 9$ — gives the total inversion count without ever comparing every pair directly.

4. Naive Brute-Force Approach

The obvious correct algorithm checks every pair directly: for every $i < j$, test whether $a[i] > a[j]$ and count the pairs that qualify.

def count_inversions_brute(values):
    n = len(values)
    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            if values[i] > values[j]:
                count += 1
    return count

sample = [5, 2, 6, 3, 1, 4]
print("Inversions (brute force):", count_inversions_brute(sample))  # Inversions (brute force): 9

This is easy to prove correct — it is a direct transcription of the definition — but it inspects every one of the $\binom{n}{2}$ pairs, giving $\Theta(n^2)$ time. It also repeats work: once you know $a[2]$ is greater than every remaining element in a sorted run, checking it against each of them individually re-derives a fact that a single sorted comparison could have delivered for many elements at once. That repeated work is exactly what the merge-sort-based approach eliminates.

5. Core Insight

Concretely: if the left half still has $k$ unconsumed elements when a right-half element is chosen next, that single placement accounts for exactly $k$ inversions, because the left half is sorted and every one of those $k$ elements is $\ge$ the one just compared, hence greater than the placed right-half element too. This is the one idea that turns an $O(n^2)$ pairwise scan into an $O(n)$ per-merge tally.

6. Manual Trace & Dry Run

Building on the recursion tree from A Concrete Example, here is exactly what happens inside each of the five merges, in the bottom-up order they actually execute:

Total inversions: $0 + 0 + 1 + 1 + 7 = 9$, matching both the brute-force count from Naive Brute-Force Approach and the recursion-tree annotation from A Concrete Example.

7. Correctness Reasoning

The proof rests on a clean partition of every inversion pair $(i, j)$ with $i < j$ and $a[i] > a[j]$ into exactly one of three disjoint categories, for any split point that divides the array into a left half $L$ and a right half $R$:

1. Both indices fall in $L$: counted by the recursive call on the left half.
2. Both indices fall in $R$: counted by the recursive call on the right half.
3. $i$ falls in $L$ and $j$ falls in $R$: counted during the merge, exactly when a right-half element is placed while left-half elements remain unconsumed.

This partition is exhaustive: every pair with $i < j$ has its two indices somewhere in the array, and because $L$ contains a contiguous prefix of indices and $R$ a contiguous suffix, any pair either has both indices in $L$, both in $R$, or the smaller index in $L$ and the larger in $R$ — the fourth combination (smaller index in $R$, larger in $L$) is impossible since $L$'s indices are all less than $R$'s. It is also non-overlapping: a given pair cannot belong to two categories at once, since "both in $L$", "both in $R$", and "one in each" are mutually exclusive by construction.

The merge step correctly counts every category-3 pair because, by induction, $L$ and $R$ arrive at the merge already internally sorted (this is the same induction merge sort itself relies on for correctness, not re-derived here). Whenever the merge chooses the next output element from $R$ while $L$ still has unconsumed elements, every one of those remaining $L$ elements is, by $L$'s sorted order, at least as large as the $L$ element most recently compared — and since that comparison already established the chosen $R$ element is smaller, it is smaller than all of them. So crediting the placement with "one inversion per remaining left element" is exact, not an approximation. Total inversions therefore equal (inversions within $L$) + (inversions within $R$) + (cross inversions counted during the merge), with no pair missed and no pair double-counted.

8. Complexity Analysis

Counting during the merge adds no new asymptotic cost: the merge step already visits every element of both halves exactly once, and incrementing a running counter is $O(1)$ extra work per comparison. So the recurrence is identical to merge sort's own:

$$T(n) = 2T(n/2) + O(n)$$

The recursion tree has $\log_2 n$ levels, each doing $O(n)$ total work across all nodes at that level (splitting plus merging), giving:

Counting inversions is therefore never more expensive, asymptotically, than sorting the array in the first place — a useful fact when deciding whether a system that already sorts its data can get an inversion count "for free" as a byproduct.

9. Implementation

The Inversion Count implementation below mirrors ordinary merge sort exactly, with one addition: whenever the merge takes the next element from the right side while left-side elements remain, it adds the number of remaining left elements to a running count.

def count_inversions(values):
    def sort_and_count(arr):
        n = len(arr)
        if n <= 1:
            return arr, 0
        mid = n // 2
        left, inv_left = sort_and_count(arr[:mid])
        right, inv_right = sort_and_count(arr[mid:])
        merged = []
        i = j = 0
        cross = 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                merged.append(left[i])
                i += 1
            else:
                # right[j] is smaller than every remaining left element:
                # every one of those elements forms an inversion with it
                cross += len(left) - i
                merged.append(right[j])
                j += 1
        merged.extend(left[i:])
        merged.extend(right[j:])
        return merged, inv_left + inv_right + cross

    _, total = sort_and_count(list(values))
    return total

sample = [5, 2, 6, 3, 1, 4]
print("Inversions:", count_inversions(sample))  # Inversions: 9
print("Sorted, no inversions:", count_inversions([1, 2, 3, 4]))          # 0
print("Reverse sorted, max inversions:", count_inversions([4, 3, 2, 1])) # 6

#include <iostream>
#include <vector>
using namespace std;

long long mergeCount(vector<int>& arr, vector<int>& temp, int left, int right) {
    if (left >= right) {
        return 0;
    }
    int mid = left + (right - left) / 2;
    long long invCount = mergeCount(arr, temp, left, mid) + mergeCount(arr, temp, mid + 1, right);

    int i = left, j = mid + 1, k = left;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            // arr[j] is smaller than every remaining left element arr[i..mid]
            invCount += (mid - i + 1);
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    for (int p = left; p <= right; ++p) {
        arr[p] = temp[p];
    }
    return invCount;
}

long long countInversions(vector<int> values) {
    if (values.empty()) {
        return 0;
    }
    vector<int> temp(values.size());
    return mergeCount(values, temp, 0, static_cast<int>(values.size()) - 1);
}

int main() {
    vector<int> sample{5, 2, 6, 3, 1, 4};
    cout << "Inversions: " << countInversions(sample) << '\n'; // Inversions: 9

    vector<int> sorted{1, 2, 3, 4};
    cout << "Sorted: " << countInversions(sorted) << '\n'; // Sorted: 0

    vector<int> reversed{4, 3, 2, 1};
    cout << "Reverse sorted: " << countInversions(reversed) << '\n'; // Reverse sorted: 6
}

import java.util.Arrays;

public class InversionCount {
    static long mergeCount(int[] arr, int[] temp, int left, int right) {
        if (left >= right) {
            return 0;
        }
        int mid = left + (right - left) / 2;
        long invCount = mergeCount(arr, temp, left, mid) + mergeCount(arr, temp, mid + 1, right);

        int i = left, j = mid + 1, k = left;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                // arr[j] is smaller than every remaining left element arr[i..mid]
                invCount += (mid - i + 1);
                temp[k++] = arr[j++];
            }
        }
        while (i <= mid) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];
        System.arraycopy(temp, left, arr, left, right - left + 1);
        return invCount;
    }

    static long countInversions(int[] values) {
        if (values.length == 0) {
            return 0;
        }
        int[] arr = Arrays.copyOf(values, values.length);
        int[] temp = new int[arr.length];
        return mergeCount(arr, temp, 0, arr.length - 1);
    }

    public static void main(String[] args) {
        int[] sample = {5, 2, 6, 3, 1, 4};
        System.out.println("Inversions: " + countInversions(sample)); // Inversions: 9

        int[] sorted = {1, 2, 3, 4};
        System.out.println("Sorted: " + countInversions(sorted)); // Sorted: 0

        int[] reversed = {4, 3, 2, 1};
        System.out.println("Reverse sorted: " + countInversions(reversed)); // Reverse sorted: 6
    }
}

Reverse Pairs

Reverse Pairs is a harder variant: count pairs $i < j$ where $a[i] > 2 \cdot a[j]$. The factor of 2 seems like a small change, but it breaks the trick from Core Insight: that trick relied on "if right's element is smaller than left's current element, it is smaller than everything left of it too" — a fact that falls directly out of the plain merge comparison $\mathit{left}[i] \le \mathit{right}[j]$. There is no way to read "$a[i] > 2 \cdot a[j]$" off that same comparison, because the merge only ever compares $\mathit{left}[i]$ against $\mathit{right}[j]$ directly, never against $2 \cdot \mathit{right}[j]$.

Crucially, this counting pass uses its own pointer into the right half, entirely separate from the pointer the ordinary merge uses afterward. Reusing the same pointer for both would be a bug: the counting pass advances its pointer based on the condition $\mathit{left}[i] > 2 \cdot \mathit{right}[j]$, which has nothing to do with the plain $\le$ comparison the merge needs — by the time counting finishes, that pointer may sit far past elements the merge still needs to place in order. Using it to drive the merge would silently skip or duplicate elements. The fix is simple: run the full counting pass first with its own pointer, discard that pointer, then run the ordinary merge from scratch with two fresh pointers.

Worked check: for [2, 4, 3, 5, 1], the only element that any earlier element beats by more than double is the last one, 1. Checking every pair against $2 \times 1 = 2$: $4 > 2$, $3 > 2$, and $5 > 2$ all qualify (three pairs), while $2 > 2$ does not (2 is not strictly greater than 2). That gives 3 reverse pairs, all sharing index $j$, which the implementation below reproduces exactly.

def count_reverse_pairs(values):
    def sort_and_count(arr):
        n = len(arr)
        if n <= 1:
            return arr, 0
        mid = n // 2
        left, count_left = sort_and_count(arr[:mid])
        right, count_right = sort_and_count(arr[mid:])

        # Counting pass BEFORE merging, with its OWN pointer j. Both halves
        # are sorted, so as left[i] grows, j only ever moves forward across
        # the whole loop -- this pass is O(len(left) + len(right)) total,
        # not a re-scan of the right half for every left element.
        count = count_left + count_right
        j = 0
        for value in left:
            while j < len(right) and value > 2 * right[j]:
                j += 1
            count += j

        # Normal merge pass, using its OWN pointers i and k. Reusing j from
        # the counting pass above would be wrong: j was advanced according
        # to the "> 2 *" condition, not the merge's "<=" condition, so it
        # may already sit past elements the merge still needs to place.
        merged = []
        i = k = 0
        while i < len(left) and k < len(right):
            if left[i] <= right[k]:
                merged.append(left[i])
                i += 1
            else:
                merged.append(right[k])
                k += 1
        merged.extend(left[i:])
        merged.extend(right[k:])
        return merged, count

    _, total = sort_and_count(list(values))
    return total

sample = [2, 4, 3, 5, 1]
print("Reverse pairs:", count_reverse_pairs(sample))            # Reverse pairs: 3
print("Sorted, no reverse pairs:", count_reverse_pairs([1, 2, 3, 4]))  # 0
print("Classic example:", count_reverse_pairs([1, 3, 2, 3, 1]))        # 2

#include <iostream>
#include <vector>
using namespace std;

long long mergeAndCount(vector<int>& arr, vector<int>& temp, int left, int right) {
    if (left >= right) {
        return 0;
    }
    int mid = left + (right - left) / 2;
    long long count = mergeAndCount(arr, temp, left, mid) + mergeAndCount(arr, temp, mid + 1, right);

    // Counting pass BEFORE merging: j starts at mid + 1 and, because both
    // halves are sorted, only moves forward as i increases across the loop.
    int j = mid + 1;
    for (int i = left; i <= mid; ++i) {
        while (j <= right && static_cast<long long>(arr[i]) > 2LL * arr[j]) {
            ++j;
        }
        count += (j - (mid + 1));
    }

    // Normal merge pass with its OWN pointers i and m -- never reuse j
    // above, it was advanced by a different condition than the merge needs.
    int i = left, m = mid + 1, k = left;
    while (i <= mid && m <= right) {
        if (arr[i] <= arr[m]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[m++];
        }
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (m <= right) temp[k++] = arr[m++];
    for (int p = left; p <= right; ++p) {
        arr[p] = temp[p];
    }
    return count;
}

long long countReversePairs(vector<int> values) {
    if (values.empty()) {
        return 0;
    }
    vector<int> temp(values.size());
    return mergeAndCount(values, temp, 0, static_cast<int>(values.size()) - 1);
}

int main() {
    vector<int> sample{2, 4, 3, 5, 1};
    cout << "Reverse pairs: " << countReversePairs(sample) << '\n'; // Reverse pairs: 3

    vector<int> sorted{1, 2, 3, 4};
    cout << "Sorted: " << countReversePairs(sorted) << '\n'; // Sorted: 0

    vector<int> classic{1, 3, 2, 3, 1};
    cout << "Classic example: " << countReversePairs(classic) << '\n'; // Classic example: 2
}

import java.util.Arrays;

public class ReversePairs {
    static long mergeAndCount(int[] arr, int[] temp, int left, int right) {
        if (left >= right) {
            return 0;
        }
        int mid = left + (right - left) / 2;
        long count = mergeAndCount(arr, temp, left, mid) + mergeAndCount(arr, temp, mid + 1, right);

        // Counting pass BEFORE merging: j only moves forward as i increases.
        int j = mid + 1;
        for (int i = left; i <= mid; i++) {
            while (j <= right && (long) arr[i] > 2L * arr[j]) {
                j++;
            }
            count += (j - (mid + 1));
        }

        // Normal merge pass with its OWN pointers -- never reuse j above.
        int i = left, m = mid + 1, k = left;
        while (i <= mid && m <= right) {
            if (arr[i] <= arr[m]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[m++];
            }
        }
        while (i <= mid) temp[k++] = arr[i++];
        while (m <= right) temp[k++] = arr[m++];
        System.arraycopy(temp, left, arr, left, right - left + 1);
        return count;
    }

    static long countReversePairs(int[] values) {
        if (values.length == 0) {
            return 0;
        }
        int[] arr = Arrays.copyOf(values, values.length);
        int[] temp = new int[arr.length];
        return mergeAndCount(arr, temp, 0, arr.length - 1);
    }

    public static void main(String[] args) {
        int[] sample = {2, 4, 3, 5, 1};
        System.out.println("Reverse pairs: " + countReversePairs(sample)); // Reverse pairs: 3

        int[] sorted = {1, 2, 3, 4};
        System.out.println("Sorted: " + countReversePairs(sorted)); // Sorted: 0

        int[] classic = {1, 3, 2, 3, 1};
        System.out.println("Classic example: " + countReversePairs(classic)); // Classic example: 2
    }
}

The counting pass adds only $O(\text{len(left)} + \text{len(right)})$ work per merge because its pointer is monotonic, so Reverse Pairs keeps the same recurrence and the same $O(n \log n)$ time as Inversion Count — the extra pass changes the constant factor, not the asymptotic complexity.

11. Testing & Edge Cases

Both implementations above are exercised against several boundary cases directly in their sample output: an already-sorted array produces zero inversions and zero reverse pairs, since no element is ever out of order relative to any later one. A reverse-sorted array of length $n$ produces the maximum possible inversion count, $n(n-1)/2$, because every one of the $\binom{n}{2}$ pairs is inverted — a useful sanity check, since any correct implementation must reproduce that exact closed form. Duplicate elements are handled correctly by the strict comparisons used throughout ($a[i] > a[j]$ and $a[i] > 2 \cdot a[j]$, not $\ge$): equal values never count as inversions or reverse pairs, and the merge's $\mathit{left}[i] \le \mathit{right}[j]$ tie-breaking rule keeps the sort itself stable without ever crediting a tie as a crossing. A single-element or empty array hits the base case directly and returns 0 without entering the merge logic at all, avoiding any division or indexing edge case.

12. Applications & Alternatives

The merge-sort-based approach here computes one batch total in a single pass over the whole array. When queries instead need to be online or incremental — for example, "how many inversions exist among the elements seen so far" after every insertion, rather than one final count over a fixed array — the Fenwick-tree sweep in Sort-by-Threshold and Event Sorting is the better fit: it supports incremental updates in $O(\log n)$ each, whereas re-running the merge-sort-based count from scratch after every insertion would cost $O(n \log n)$ per update. Choose the merge-sort-based technique for a single batch count over static data, and the Fenwick-tree sweep when the data or the query point changes incrementally.

13. Exercises & Mastery

Easy

1. Compute the inversion count of [9, 1, 0, 5, 4] by hand, then verify your answer with the implementation from Implementation.

Medium

1. Compute the reverse-pair count of [3, 1, 2, 6, 4] by hand (pairs $i < j$ with $a[i] > 2 \cdot a[j]$), tracing the separate counting pass pointer explicitly for each left element before checking your answer against the implementation.

Hard

1. Design (conceptually, no need to fully implement) a merge-sort augmentation that counts triples $i < j < k$ satisfying $a[i] > a[j] > a[k]$ (a "descending triple"). Think about what information the combine step needs to carry forward from smaller subproblems to answer a three-element condition instead of a two-element one, and whether a single extra counting pass, like Reverse Pairs uses, is enough, or whether the combine step needs to track more than a single running count.

Review rhythm: tomorrow, reconstruct the merge-step counting insight and the Reverse Pairs pointer separation without notes; next week, implement both algorithms from memory in one language; several weeks later, recognize this same "augment the combine step" idea in an unfamiliar counting problem before checking whether this lesson's technique applies.

14. Summary Cheat Sheet

• An inversion is a pair $i < j$ with $a[i] > a[j]$; it measures how far an array is from sorted.
• Merge sort's combine step already inspects every cross-half relationship once; augmenting it to count inversions costs no extra asymptotic time.
• Core insight: placing a right-half element ahead of $k$ remaining left-half elements contributes exactly $k$ inversions in one step, because both halves are already sorted.
• Total inversions = (left-half inversions) + (right-half inversions) + (cross inversions counted during merge) — an exhaustive, non-overlapping partition.
• Complexity matches plain merge sort exactly: $T(n) = 2T(n/2) + O(n)$, giving $O(n \log n)$ time and $O(n)$ auxiliary space.
• Reverse Pairs ($a[i] > 2 \cdot a[j]$) cannot reuse the plain merge comparison; it needs a separate, amortized-linear counting pass with its own pointer, run before the ordinary merge with its own separate pointers.
• For a single batch count over static data, use the merge-sort-based technique here; for online/incremental counting as data or queries arrive, use the Fenwick-tree sweep instead.