Counting via Merge Sort

Description

Merge-sort counting answers "how many pairs are out of order?" in O(n log n). Those pairs are called inversions, and variants such as reverse pairs work the same way. You count while merge sort runs. When two sorted halves are merged, the left-half elements still waiting are all bigger than the right-half element being placed. Each of them forms an out-of-order pair with it, so a whole block of pairs is counted in one step.

We'll go from simple to more technical:

1. The pattern: count during the merge, while both halves are sorted.
2. A second flavor: when the counting condition differs from the sort order, count in its own pass.
3. Where "how out of order is this?" is a real metric.
4. The bugs that only show up on large or deep inputs.

The approach

Checking every pair is O(n^2): about 5 billion comparisons for 100,000 elements. Merge sort does better because its merge step is where left-half and right-half elements meet. Both halves are sorted at that point. So when a right-half element is smaller than the next left-half element, it's also smaller than every left-half element after that one.

Merging the sorted halves [2, 5, 8] and [1, 6, 7]:

That's 5 pairs found with 6 steps, not 9 pair checks.

long mergeSortCount(int[] nums, int lo, int hi) {
    if (lo >= hi) return 0;
    int mid = lo + (hi - lo) / 2;
    long count = mergeSortCount(nums, lo, mid) + mergeSortCount(nums, mid + 1, hi);
    return count + mergeCount(nums, lo, mid, hi);   // cross-half pairs, counted during the merge
}

long mergeCount(int[] nums, int lo, int mid, int hi) {
    // standard merge, except: whenever an element from the right half is taken
    // because it's smaller than the current left element, every remaining
    // element in the left half (there are `mid - i + 1` of them) forms an
    // out-of-order pair with it - add that count.
}

def merge_sort_count(nums: list[int], lo: int, hi: int) -> int:
    if lo >= hi:
        return 0
    mid = (lo + hi) // 2
    count = merge_sort_count(nums, lo, mid) + merge_sort_count(nums, mid + 1, hi)
    return count + merge_count(nums, lo, mid, hi)   # cross-half pairs, counted during the merge


def merge_count(nums: list[int], lo: int, mid: int, hi: int) -> int:
    # standard merge, except: whenever an element from the right half is taken
    # because it's smaller than the current left element, every remaining
    # element in the left half (there are mid - i + 1 of them) forms an
    # out-of-order pair with it - add that count.
    ...

Pairs inside one half were already counted by the recursive call that sorted that half. So the merge only counts pairs across the two halves, and each count is one subtraction, mid - i + 1, not a loop.

A second flavor: a scaled comparison needs its own pass

Reverse Pairs counts pairs where nums[i] > 2 * nums[j], with i in the left half and j in the right half. The merge only ever compares nums[i] with nums[j], so it doesn't answer this question. Instead, run a separate two-pointer pass over the two sorted halves before the normal merge:

int j = mid + 1;
for (int i = lo; i <= mid; i++) {
    while (j <= hi && nums[i] > 2L * nums[j]) j++;
    count += j - (mid + 1);   // every right-half element scanned past so far qualifies with nums[i]
}
// ...then merge lo..hi normally, exactly as in plain inversion counting

j = mid + 1
for i in range(lo, mid + 1):
    while j <= hi and nums[i] > 2 * nums[j]:
        j += 1
    count += j - (mid + 1)   # every right-half element scanned past so far qualifies with nums[i]
# ...then merge lo..hi normally, exactly as in plain inversion counting

j never moves back. Both halves are sorted, so as i moves right, nums[i] only grows. Any right-half element it already beat, it still beats. That keeps the extra pass O(n) per level.

Where you'll see it

"How far is this data from sorted?" is a real measure. For example, how far does an event log stray from the order in which events arrived? This technique answers it in O(n log n). It also measures how much two rankings disagree.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. A merge counts correctly but never writes the merged result back into the array. What breaks?

2. Why does the count need a long for 100,000 elements?

3. Why does Reverse Pairs need an extra pass when plain inversion counting doesn't?

Key takeaways

• When a right-half element is taken, every left-half element still waiting is bigger. Count them all at once with mid - i + 1.
• The merge counts only pairs across the halves. The recursion already counted pairs inside each half.
• Write the merged result back, because higher levels rely on sorted halves.
• Use a long for the count.
• A condition the merge doesn't compare directly, like > 2 *, needs its own pass over the sorted halves.