Counting pairs with merge sort

Merge sort can count pairs while it sorts. Many counting questions ask how many pairs i < j satisfy a condition between an earlier and a later value: inversions, where a[i] > a[j], or reverse pairs, where a[i] > 2 · a[j]. Trying every pair costs O(n²). Merge sort splits the array, sorts both halves and merges them, and at every merge both halves are sorted, so the pairs that cross the middle can be counted with pointers that only move forward: O(n) per level and O(n log n) in all. This lesson’s problem counts reverse pairs in a trading log, where they are called big drops.

The problem: big drops in a profit-and-loss log

1. [3, 1, 4, 1, 5] gives 3: day 0 with day 1, day 0 with day 3, and day 2 with day 3.
2. [-2, -5, 1, -3] gives 4. The comparison is signed, so −2 > −10 makes days 0 and 1 a big drop.
3. [2147483647, 1073741824] gives 0, because twice the second figure is 2,147,483,648, which a 32-bit integer cannot hold.

The brute force: every pair

Check every pair i < j. That is n(n − 1)/2 checks, correct by construction and the referee for faster code, but 4,999,950,000 checks at n = 10⁵:

# Big drops by brute force: check every pair of days i < j for pnl[i] > 2 * pnl[j]. Then how many pairs that is.
import random


def big_drops_brute(pnl):
    """Counts the pairs i < j with pnl[i] > 2 * pnl[j], and the pairs checked: n(n - 1)/2 of them."""
    count = checked = 0
    for j in range(len(pnl)):
        for i in range(j):
            checked += 1
            if pnl[i] > 2 * pnl[j]:
                count += 1
    return count, checked


for pnl in ([3, 1, 4, 1, 5], [-2, -5, 1, -3], [2147483647, 1073741824]):
    print(pnl, "->", big_drops_brute(pnl)[0])

rng = random.Random(6)
for n in (1_000, 2_000):
    days = [rng.randint(-2**31, 2**31 - 1) for _ in range(n)]
    count, checked = big_drops_brute(days)
    print(f"n = {n:,}: {checked:,} pairs checked, {count:,} big drops")
n = 100_000
print(f"n = {n:,}: {n * (n - 1) // 2:,} pairs to check")

[3, 1, 4, 1, 5] -> 3
[-2, -5, 1, -3] -> 4
[2147483647, 1073741824] -> 0
n = 1,000: 499,500 pairs checked, 255,924 big drops
n = 2,000: 1,999,000 pairs checked, 952,639 big drops
n = 100,000: 4,999,950,000 pairs to check

The run makes 499,500 checks for 1,000 days and 1,999,000 for 2,000: twice the days, four times the work. On 1,000 random days the log already holds 255,924 big drops, so the answer itself is large, and for 10⁵ days it can pass what a 32-bit integer holds.

What to notice

The condition compares an earlier value with a later one, and the count does not depend on how the values on each side are ordered among themselves. If the first half and the second half of the log were each sorted, then as the left value grows, the right values below half of it can only grow in number, so one sweep with two pointers would count every big drop that crosses the middle. Merge sort produces exactly those sorted halves, at every level.

Counting while merge sort sorts Pro: opens with a Pro, Premium or Ultimate pass