Merge sort with counting

43 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

The list 1, 3, 2, 3, 1. Count the "reverse pairs": positions i < j where nums[i] > 2 × nums[j]. Checking by hand: 3 (index 1) > 2 × 1 (index 4), and 3 (index 3) > 2 × 1 (index 4). Two pairs.

By hand you check every pair: 10 pairs for 5 numbers, n(n − 1)/2 in general. For fifty thousand numbers that is over a billion checks. The problem is that the left element must be compared with every right element one at a time, because the right side is in no particular order.

Now imagine the right part were sorted. For a left element 3, the right elements satisfying 3 > 2r, that is r < 1.5, form a prefix of the sorted right part. Counting a prefix is one scan that stops early, and if the left part is also sorted, the stopping point only moves forward as the left element grows. Sorting both halves turns pair checking into a two-pointer walk.

Build the structure, one piece at a time

The structure is merge sort, with one extra counting step glued into each merge.

Piece 1: split. Cut the list in half: left = 1, 3 and right = 2, 3, 1. Recursively sort and count inside each half. Inside the left half there are no pairs. Inside the right half, 3 > 2 × 1 gives one pair, and it becomes sorted: 1, 2, 3. The left half sorts to 1, 3.

Piece 2: count across the halves. Both halves are sorted. Walk a pointer r through the right half for each left element, advancing while nums[left] > 2 × nums[r]; the number of right elements passed is this left element's count. Because left elements come in increasing order, r never moves backwards.

Piece 3: merge. Now merge the two sorted halves in the usual way: take the smaller front element each time: 1, 1, 2, 3, 3. The merged list is sorted and ready for the level above.

Total: 1 (inside the right half) + 1 (across) = 2 pairs.

Why it is correct

The invariant: when a call returns, its range is sorted and the pairs entirely inside that range have been counted.

Every pair (i, j) lives in exactly one place: both in the left half, both in the right half, or one in each. The first two are counted by the recursive calls (by the invariant). For the cross pairs, sorting within a half does not change which values are in it, and a cross pair is just a left value and a right value, so counting over the sorted halves counts exactly the cross pairs. The two-pointer walk is exact because for a fixed left value the qualifying right values are a prefix of the sorted right half, and that prefix grows as the left value grows.

count(range) = count(left) + count(right) + #{(l, r) : l in left, r in right, l > 2r}

Counting must happen before the merge, because the merge mixes the halves and the information about which side a value came from is lost.

Why it is fast

At each level of the recursion, the counting walk and the merge each pass over the n elements once. Halving the range each time gives log₂ n levels.

time = O(n) per level × log₂ n levels = O(n log n)

For fifty thousand numbers that is about 800 000 steps instead of a billion.

How to recognise it in an interview

The cues are "count pairs with i < j and some inequality", "count inversions", "how many smaller elements after each element", "count of range sums". Whenever the count is over ordered pairs and the inequality involves comparing values, think of sorting halves and counting across. Say: "I run merge sort and count cross pairs between the two sorted halves with a two-pointer walk before merging."

Reverse Pairs is the example above. Count of Smaller Numbers After Self needs a count per element, so the merge carries original indices along and credits each left element with the number of right elements that jumped ahead of it. Count of Range Sum applies the same counting to the sorted prefix-sum array.

02The idea in one line

While merging, count cross pairs that violate the order.

Reach for it when: Count inversions, reverse pairs, count of smaller after self, range sums.

Cost: O(n log n) time.

03The walk-through, step by step

The video works one example: Reverse Pairs on [1,3,2,3,1]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Sort each half recursively; count cross pairs while merging
2. left 1: no right value r with 1 > 2·r
3. left 2: no right value r with 2 > 2·r
4. left 3: 1 right value with 3 > 2·r → pairs += 1
5. Within each half the pairs were counted in the recursive calls (1 there: 3 > 2·1)
6. Merge: take 1 from the left
7. Merge: take 1 from the right
8. Merge: take 2 from the left
9. Merge: take 3 from the left
10. Merge: take 3 from the right
11. Total reverse pairs: 2 (3>2·1, 3>2·1 from each 3)
12. Counting rides on the merge: O(n log n)

04Asked at Google

5 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Sorting: Custom comparator / key sort, Cyclic sort (1..n placement), Quickselect (kth element), Bucket / counting sort.