Merge Sort & Inversion Counting
Merge sort is the cleanest divide-and-conquer algorithm there is: split the array in half, sort each half, merge the two sorted halves. Every part of it can be analysed exactly. It is stable, its worst case is with no probability involved, it is the natural sort for linked lists and for data that does not fit in memory, and its merge step — two pointers walking two sorted sequences — is one of the most reused ideas in computing. Database sort-merge joins, LSM-tree compaction, external sorting, Timsort and the Linux kernel's list sorting are all merges at heart.
The second half of this page is about what merge sort computes along the way. While merging, every time an element of the right half overtakes elements of the left half, it reveals exactly how many inversions it was part of. That turns merge sort into an algorithm for counting inversions, and the same trick solves a family of "count the pairs such that…" problems: count of smaller numbers after self, reverse pairs, count of range sum.
Why this exists
The elementary sorts are quadratic for a structural reason: each adjacent swap removes at most one inversion, and a random array has of them. To do better an algorithm must fix many inversions per step. Merge sort does it by never comparing elements that are already known to be in order: once the two halves are sorted, a single linear pass merges them, and that pass implicitly resolves every inversion between the halves — up to of them — in comparisons or fewer.
John von Neumann described merge sort in 1945, in his work on the EDVAC; it is one of the first algorithms ever written for a stored-program computer. It came out of the needs of the time: data lived on magnetic tape, which can only be read sequentially, and merging is the one sorting operation that needs nothing but sequential reads and writes. That property is why merge sort, in its external form, is still how databases and MapReduce frameworks sort data larger than RAM. Knuth's Volume 3 (§5.2.4 for internal merging, §5.4 for external) is the classic treatment.
In memory, merge sort competes with quicksort and usually loses on raw speed for arrays of primitives, because it needs an auxiliary buffer and moves every element at every level. It wins whenever stability or a guaranteed worst case matters, whenever the data is a linked list, and whenever the input already contains sorted runs — which is why Python, Java (for objects), JavaScript engines and Android all sort with Timsort, a run-adaptive merge sort.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "Sort a linked list", "in time and extra space" | Bottom-up merge sort on the list (LeetCode 148) |
| "Stable sort", "keep the original order of equal elements", guaranteed worst case | Merge sort (or the library's stable sort, which is merge-based) |
| "Count pairs with ", "number of inversions", "minimum adjacent swaps" | Merge sort with a counter: add mid - i whenever the right element wins |
| "For each element, count the smaller elements to its right" | Merge sort on indices, accumulating per element (LeetCode 315) |
| "Count pairs with " for a monotone condition | Count across halves with two pointers before merging (reverse pairs, range sums) |
| "Merge sorted lists / files / streams" | -way merge with a min-heap, |
| "The data does not fit in memory", "sort a 100 GB file with 1 GB of RAM" | External merge sort: sorted runs, then -way merges |
| "Already partly sorted", "concatenation of sorted blocks" | Natural merge sort / Timsort: merge the existing runs |
| "Kendall tau distance", "how different are two rankings" | Inversions of one ranking relative to the other |
Intuition & first principles
The merge
Suppose two piles of exam papers are each sorted by score. To produce one sorted pile, look at the top paper of each pile, take the lower-scored one, and repeat. Each step does one comparison and outputs one paper; when a pile runs out, the rest of the other pile goes on unchanged. Two sorted piles of sizes and merge in at most comparisons.
Precisely: merge takes sorted L[0..m-1] and R[0..k-1] and produces their sorted union. It keeps indices and ; while both are in range it outputs L[i] if L[i] <= R[j], else R[j], advancing that index; then it copies whatever remains. This is Family C of Two Pointers. The <= (ties go to the left) is what makes the merge — and therefore merge sort — stable: among equal keys, everything from the left half, which came earlier in the input, is output first.
Divide and conquer
Merge needs sorted inputs. Where do they come from? Recursively: an array of length 0 or 1 is sorted; any longer array is split at , both halves are sorted recursively, and the results are merged. That is top-down merge sort.
You can also build it from the bottom: every single element is a sorted run of length 1; merge neighbouring runs pairwise into runs of length 2, then 4, then 8, until one run covers the array. That is bottom-up merge sort. It does the same kind of work with no recursion at all, which makes it the natural form for linked lists, for external sorting, and for anyone worried about stack depth.
What a merge learns about inversions
When the merge outputs R[j] while L[i..m-1] are still waiting, R[j] is smaller than every one of those waiting elements (they are sorted, and L[i] > R[j]). Each of them came before R[j] in the original array, so each forms an inversion with it. Adding to a counter at that moment counts every inversion between the two halves exactly once. Inversions within each half were counted by the recursive calls. That is the whole inversion-counting algorithm: merge sort plus one line.
Mechanics
Top-down merge sort
flowchart TD
R["[38, 27, 43, 3, 9, 82, 10]<br/>→ [3, 9, 10, 27, 38, 43, 82]"] --> A["[38, 27, 43]<br/>→ [27, 38, 43]"]
R --> B["[3, 9, 82, 10]<br/>→ [3, 9, 10, 82]"]
A --> A1["[38]"]
A --> A2["[27, 43]<br/>→ [27, 43]"]
A2 --> A21["[27]"]
A2 --> A22["[43]"]
B --> B1["[3, 9]<br/>→ [3, 9]"]
B --> B2["[82, 10]<br/>→ [10, 82]"]
B1 --> B11["[3]"]
B1 --> B12["[9]"]
B2 --> B21["[82]"]
B2 --> B22["[10]"]
Each node splits on the way down (at ) and merges on the way up; the arrow inside a label shows the node's merged result. The merges happen in post-order. Trace of the six merges on [38, 27, 43, 3, 9, 82, 10] (computed by script; "cross inversions" is the mid - i counter):
| Merge # | Left run | Right run | Comparisons | Cross inversions | Result |
|---|---|---|---|---|---|
| 1 | [27] | [43] | 1 | 0 | [27, 43] |
| 2 | [38] | [27, 43] | 2 | 1 | [27, 38, 43] |
| 3 | [3] | [9] | 1 | 0 | [3, 9] |
| 4 | [82] | [10] | 1 | 1 | [10, 82] |
| 5 | [3, 9] | [10, 82] | 2 | 0 | [3, 9, 10, 82] |
| 6 | [27, 38, 43] | [3, 9, 10, 82] | 6 | 9 | [3, 9, 10, 27, 38, 43, 82] |
Totals: 13 comparisons and 11 inversions. Merge 5 needed only 2 comparisons because the left run [3, 9] was exhausted after two steps; the right run was then copied with no comparisons. Merge 6 found 9 inversions: each of 3, 9 and 10 overtook all three elements of [27, 38, 43].
Bottom-up merge sort
flowchart LR
P0["width 1:<br/>[38] [27] [43] [3] [9] [82] [10]"] --> P1["width 2:<br/>[27, 38] [3, 43] [9, 82] [10]"]
P1 --> P2["width 4:<br/>[3, 27, 38, 43] [9, 10, 82]"]
P2 --> P3["width 8:<br/>[3, 9, 10, 27, 38, 43, 82]"]
Pass with width merges a[lo..lo+w-1] with a[lo+w..lo+2w-1] for , clipping the right run at ; a final run with no partner is carried over unchanged. Trace (computed by script):
| Width | Left run | Right run | Comparisons | Cross inversions | Merged |
|---|---|---|---|---|---|
| 1 | [38] | [27] | 1 | 1 | [27, 38] |
| 1 | [43] | [3] | 1 | 1 | [3, 43] |
| 1 | [9] | [82] | 1 | 0 | [9, 82] |
| 1 | [10] | — | 0 | 0 | carried over |
| 2 | [27, 38] | [3, 43] | 3 | 2 | [3, 27, 38, 43] |
| 2 | [9, 82] | [10] | 2 | 1 | [9, 10, 82] |
| 4 | [3, 27, 38, 43] | [9, 10, 82] | 6 | 6 | [3, 9, 10, 27, 38, 43, 82] |
Totals: 14 comparisons and 11 inversions. The inversion count is a property of the input, so both versions find 11; the comparison count depends on how the array is split, so top-down (13) and bottom-up (14) differ. For a power of two the two versions split identically.
The last merge, step by step:
| Step | i | j | L[i] | R[j] | Output | Inversions added |
|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 3 | 9 | 3 (left) | 0 |
| 2 | 1 | 0 | 27 | 9 | 9 (right) | 3 (27, 38, 43 are waiting) |
| 3 | 1 | 1 | 27 | 10 | 10 (right) | 3 |
| 4 | 1 | 2 | 27 | 82 | 27 (left) | 0 |
| 5 | 2 | 2 | 38 | 82 | 38 (left) | 0 |
| 6 | 3 | 2 | 43 | 82 | 43 (left) | 0 |
| — | 4 | 2 | — | 82 | copy 82 | 0 |
Memory layout of a practical merge
A textbook merge allocates new lists at every call. A practical one allocates a single auxiliary buffer aux of size once. To merge a[lo..mid-1] with a[mid..hi-1]: copy a[lo..hi-1] into aux[lo..hi-1], then merge from aux back into a. Two refinements are common:
- Skip the merge if the halves are already in order: if
a[mid-1] <= a[mid], the concatenation is sorted. This one comparison makes merge sort run in on sorted input (each level costs one comparison per merge) and is in most production implementations. - Copy only the left half: copy
a[lo..mid-1]into a buffer of size and merge forward intoa; the right half never needs copying because the write position can never overtake the unread right elements. This halves both the buffer and the copying. Timsort uses this, copying whichever run is smaller.
The ladder: brute force → better → optimal
The task: sort comparable elements (and, for the second half of the page, count inversions).
Rung 1 — quadratic sort, . Insertion sort sorts and, as proved in the previous lesson, its number of shifts is the inversion count. For counting inversions the brute force is the double loop over all pairs, comparisons. At that is about — too slow for a 1-second limit in any language.
Rung 2 — split once, . Insertion-sort the two halves separately ( shifts on average instead of ), then merge them in comparisons. Halving once halves the quadratic work. This is the key observation: sorting is superadditive, so splitting pays.
Rung 3 — split recursively, . If splitting once halves the work, split the halves too, all the way down to single elements. Now the work is the merging alone: about per level, levels. For : about comparisons instead of . Counting inversions comes free with one extra addition per merge step.
Rung 4 — engineering the constant. Allocate one buffer, not one per call; insertion-sort runs below about 16–32 elements (recursion overhead dominates there); skip merges whose halves are already in order; copy only the smaller run; detect natural runs. These give no asymptotic gain but routinely make merge sort 2–3 times faster, and the last two make it adaptive. Fully engineered, this rung is Timsort, the subject of Sorting in the Real World.
Rung 5 — the lower bound. No comparison sort can beat comparisons in the worst case (Non-Comparison Sorts & the Lower Bound). Merge sort's worst case is , within about of that bound when is a power of two. In comparisons, merge sort is essentially optimal; what it pays for is memory traffic.
| Rung | Sort time | Inversion count time | Extra space | Stable | Notes |
|---|---|---|---|---|---|
| Insertion sort / pair loop | yes | Fine for a few thousand | |||
| Split once + merge | shifts | yes | Shows why splitting pays | ||
| Merge sort | yes | Worst case guaranteed | |||
| Engineered (Timsort) | , on runs | — | yes | What libraries ship | |
| Lower bound | for comparison-based methods | — | — | Merge sort is within of it |
Correctness
The merge invariant
Lemma (merge). Let L[0..m-1] and R[0..k-1] be sorted. At the start of each iteration of the merge loop, the output out[0..i+j-1] is sorted and consists of the smallest elements of the multiset — specifically L[0..i-1] and R[0..j-1] — and every element of out is every element of L[i..] and R[j..].
Initialisation. , out is empty.
Maintenance. Suppose both L[i] and R[j] exist and L[i] <= R[j]. Since L is sorted, L[i] is the smallest of L[i..]; since R is sorted and L[i] <= R[j], it is also everything in R[j..]. So L[i] is a minimum of the remaining elements, and by the invariant it is everything already output. Appending it keeps out sorted and preserves both parts of the invariant. The case L[i] > R[j] is symmetric.
Termination. Each iteration increases by one. When one input is exhausted, the remainder of the other is sorted and, by the invariant, everything in out; appending it gives the sorted union.
Stability of the merge. Take two elements with equal keys. If both come from the same input, they are output in their order within that input (each input is consumed front to back). If comes from L and from R, then when both are at the front, L[i] <= R[j] holds, so goes first. Since L is the left half — earlier in the original array — equal keys keep their original order. Using < instead of <= sends first and breaks stability while still sorting.
Merge sort
Theorem. Top-down merge sort returns the elements of a[lo..hi-1] in sorted order, and does so stably.
Proof by strong induction on . For the range is already sorted and the algorithm returns it unchanged. For , gives two ranges of sizes and , both at least 1 and strictly less than . By the induction hypothesis the recursive calls sort them stably. By the merge lemma the merge produces their sorted union, stably, with the left range's elements first among equals — which, combined with the stability of each half, preserves the original relative order of every pair of equal keys.
Bottom-up merge sort is proved by an invariant on passes: before the pass with width , each block a[t·w .. (t+1)·w - 1] (the last one possibly shorter) is sorted. For it is trivial; the merge lemma takes it from to ; the loop stops when , when the single block is the whole array.
Inversion counting
Theorem. Merge sort with the counter inv += mid - i (added whenever the right element is output) returns , the number of pairs with .
Proof by strong induction. Partition the inversions of a[lo..hi-1] into three classes: both indices in the left half, both in the right half, and cross inversions with in the left half and in the right. The recursive calls count the first two classes (induction hypothesis). Sorting each half does not change which cross pairs are inversions, because it only permutes elements within a half — every left element still precedes every right element in the original order. So it remains to show that the merge counts cross inversions exactly.
Fix a right element . When the merge outputs from position R[j], the elements still waiting in the left run are L[i..m-1]. Every one of them is : L[i] > R[j] triggered the right branch, and L is sorted. Every left element already output, L[0..i-1], is : each was output while (or a smaller right element) was waiting, which required it to be that element. So the left elements greater than are exactly L[i..m-1], and = mid - i is the number of cross inversions whose second element is . If is output in the copy-the-rest phase, the left run is empty and the count is right. Summing over all right elements counts every cross inversion exactly once.
Note the role of <=: with equal keys, the left copy is output first, so an equal pair is not counted. That matches the definition (strict ). Using < would count equal pairs as inversions.
Complexity
The recurrence
Let be the worst-case number of comparisons. The two recursive calls cost and the merge at most :
For a quick asymptotic answer, write the simplified recurrence and solve it two ways (see Complexity Analysis for both methods).
Recursion tree. The root costs . Its two children cost each — in total. The four grandchildren cost each — again. Level has subproblems of size , total cost . The leaves are at depth . So the total is per level times levels: exactly when is a power of two (with ).
flowchart TD
L0["level 0: one problem of size n<br/>cost n"] --> L1["level 1: 2 problems of size n/2<br/>cost 2 × n/2 = n"]
L1 --> L2["level 2: 4 problems of size n/4<br/>cost 4 × n/4 = n"]
L2 --> LD["level d: 2^d problems of size n/2^d<br/>cost n"]
LD --> LL["level lg n: n leaves of size 1<br/>cost 0"]
LL --> TOT["total: n per level × lg n levels = n lg n"]
Master theorem. For with , : , and . That is case 2, which gives . The intuition matches the tree: when the work per level is constant, the answer is (work per level) × (number of levels).
Exact comparison counts
- Merging sorted runs of sizes and takes between comparisons (one run is entirely smaller than the other) and (the runs interleave to the end).
- Worst case of top-down merge sort: . For : ; for : 8,977; for : . This was checked by enumerating all permutations for . Curiously, it is exactly the number of comparisons binary insertion sort makes, — two very different algorithms with identical worst-case comparison counts.
- Best case for : , when every merge finds one run entirely below the other (for example, already sorted input without the skip-merge check). For : 12.
- Average case: about ; the precise coefficient oscillates slightly with (Flajolet and Golin, 1994). Measured over 50 random permutations of 1,024 elements: 8,947 comparisons on average, against .
- Lower bound for any comparison sort: , which is . For : against merge sort's worst case 8,977 — within 5.3%.
Top-down and bottom-up have the same worst case when is a power of two. For other bottom-up can be slightly worse, because its last merge can be badly unbalanced (a run of against a short remainder): on the 7-element example it used 14 comparisons to top-down's 13.
Space
- Auxiliary array: for the standard array merge (or when only one run is copied). This is merge sort's main cost and the reason it is not used for primitives in most libraries.
- Stack: top-down recursion depth is , so — about 30 frames for a billion elements, never a problem. Bottom-up uses .
- Linked lists: extra space (bottom-up) or (top-down recursion), because merging two lists only relinks nodes. See Variations.
In-place merging: possible, rarely worth it
Can the merge be done without the buffer? Yes, but at a price:
- Rotation-based merge: find the median of the left run, binary-search its position in the right run, rotate the middle block, recurse on both sides. per merge, for the whole sort. This is what
std::inplace_mergeandstd::stable_sortfall back to when they cannot allocate a buffer — the standard specifies forstable_sortwith enough memory and without. - Linear-time stable in-place merging exists (Kronrod 1969; Huang and Langston, "Practical In-Place Merging", CACM 1988), and block merge sorts such as WikiSort and GrailSort build an in-place stable sort on it. The constants are large and the code is long; libraries prefer to allocate.
Constants and cache behaviour
Merge sort reads and writes memory sequentially: each merge streams two input runs and one output run, a pattern hardware prefetchers handle at close to memory bandwidth. That makes merge sort cache-friendly in the sense of avoiding random access, but it moves every element at every level — element moves, plus the copying into aux — whereas quicksort moves only the elements that are on the wrong side of a pivot. For large arrays of small keys that extra memory traffic is why a well-implemented quicksort is typically faster. For arrays of pointers to large objects, or when comparisons are expensive (strings, user-defined comparators), the balance shifts towards merge sort, which does fewer comparisons than quicksort on average ( against quicksort's ). The cache-oblivious refinement is to merge in blocks that fit in cache, or to use a multiway merge; external sorting takes that idea to disk.
Implementation
The canonical block implements top-down and bottom-up merge sort generically with a comparator and a single auxiliary buffer; both return the inversion count they discover along the way. Tests: the trace input, edge cases, stability on records, and a randomised comparison against the built-in sort and a brute-force inversion count.
import random
from typing import Any, Callable
def identity(x: Any) -> Any:
return x
def merge(a: list, aux: list, lo: int, mid: int, hi: int, key: Callable) -> int:
"""Merge sorted a[lo:mid] and a[mid:hi] in place via aux. Return the cross inversions."""
aux[lo:hi] = a[lo:hi]
i, j, inv = lo, mid, 0
for k in range(lo, hi):
if i < mid and (j >= hi or key(aux[i]) <= key(aux[j])): # <= : ties go left -> stable
a[k] = aux[i]
i += 1
else:
a[k] = aux[j]
j += 1
inv += mid - i # aux[i:mid] are all > this element
return inv
def merge_sort(a: list, key: Callable = identity) -> int:
"""Top-down merge sort, stable, in place. Returns the number of inversions."""
aux = list(a)
def sort(lo: int, hi: int) -> int:
if hi - lo <= 1:
return 0
mid = (lo + hi) // 2
inv = sort(lo, mid) + sort(mid, hi)
if key(a[mid - 1]) <= key(a[mid]): # halves already in order: no cross inversions
return inv
return inv + merge(a, aux, lo, mid, hi, key)
return sort(0, len(a))
def merge_sort_bottom_up(a: list, key: Callable = identity) -> int:
"""Bottom-up merge sort, stable, no recursion. Returns the number of inversions."""
n = len(a)
aux = list(a)
inv, width = 0, 1
while width < n:
for lo in range(0, n - width, 2 * width): # only blocks that have a right partner
mid, hi = lo + width, min(lo + 2 * width, n)
inv += merge(a, aux, lo, mid, hi, key)
width *= 2
return inv
def inversions_naive(a: list) -> int:
return sum(1 for i in range(len(a)) for j in range(i + 1, len(a)) if a[i] > a[j])
if __name__ == "__main__":
trace = [38, 27, 43, 3, 9, 82, 10]
for sort in (merge_sort, merge_sort_bottom_up):
b = list(trace)
assert sort(b) == 11 and b == [3, 9, 10, 27, 38, 43, 82]
for data, inv in (([], 0), ([1], 0), ([2, 2, 2], 0), ([5, 2, 4, 6, 1, 3], 9),
(list(range(8, 0, -1)), 28), (list(range(10)), 0)):
b = list(data)
assert sort(b) == inv and b == sorted(data), (sort.__name__, data)
recs = [(4, "a"), (2, "b"), (4, "c"), (1, "d"), (2, "e")]
b = list(recs)
sort(b, key=lambda r: r[0])
assert b == [(1, "d"), (2, "b"), (2, "e"), (4, "a"), (4, "c")] # stable
rng = random.Random(7)
for _ in range(300):
n = rng.randint(0, 40)
data = [(rng.randint(0, 9), idx) for idx in range(n)]
keys = [r[0] for r in data]
expected = sorted(data, key=lambda r: r[0])
for sort in (merge_sort, merge_sort_bottom_up):
b = list(data)
sort(b, key=lambda r: r[0])
assert b == expected
k = list(keys)
assert sort(k) == inversions_naive(keys)
print("ok")
import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;
public class MergeSort {
record Rec(int key, char tag) {}
/** Merge sorted a[lo..mid-1] and a[mid..hi-1] via aux. Returns the cross inversions. */
static <T> long merge(T[] a, T[] aux, int lo, int mid, int hi, Comparator<? super T> c) {
System.arraycopy(a, lo, aux, lo, hi - lo);
int i = lo, j = mid;
long inv = 0;
for (int k = lo; k < hi; k++) {
if (i < mid && (j >= hi || c.compare(aux[i], aux[j]) <= 0)) { // ties go left: stable
a[k] = aux[i++];
} else {
a[k] = aux[j++];
inv += mid - i;
}
}
return inv;
}
static <T> long sort(T[] a, T[] aux, int lo, int hi, Comparator<? super T> c) {
if (hi - lo <= 1) return 0;
int mid = (lo + hi) >>> 1;
long inv = sort(a, aux, lo, mid, c) + sort(a, aux, mid, hi, c);
if (c.compare(a[mid - 1], a[mid]) <= 0) return inv; // already in order
return inv + merge(a, aux, lo, mid, hi, c);
}
/** Top-down merge sort, stable. Returns the number of inversions. */
static <T> long mergeSort(T[] a, Comparator<? super T> c) {
return sort(a, a.clone(), 0, a.length, c);
}
/** Bottom-up merge sort, stable, no recursion. Returns the number of inversions. */
static <T> long mergeSortBottomUp(T[] a, Comparator<? super T> c) {
int n = a.length;
T[] aux = a.clone();
long inv = 0;
for (int width = 1; width < n; width *= 2) {
for (int lo = 0; lo < n - width; lo += 2 * width) {
int mid = lo + width, hi = Math.min(lo + 2 * width, n);
inv += merge(a, aux, lo, mid, hi, c);
}
}
return inv;
}
static long inversionsNaive(Integer[] a) {
long cnt = 0;
for (int i = 0; i < a.length; i++) for (int j = i + 1; j < a.length; j++) if (a[i] > a[j]) cnt++;
return cnt;
}
static void check(boolean ok, String msg) {
if (!ok) throw new AssertionError(msg);
}
static Integer[] box(int... xs) {
return Arrays.stream(xs).boxed().toArray(Integer[]::new);
}
static <T> long run(int which, T[] a, Comparator<? super T> c) {
return which == 0 ? mergeSort(a, c) : mergeSortBottomUp(a, c);
}
public static void main(String[] args) {
Comparator<Integer> nat = Comparator.naturalOrder();
Comparator<Rec> byKey = Comparator.comparingInt(Rec::key);
int[][] cases = {{}, {1}, {2, 2, 2}, {5, 2, 4, 6, 1, 3}, {8, 7, 6, 5, 4, 3, 2, 1}, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}};
long[] invs = {0, 0, 0, 9, 28, 0};
for (int w = 0; w < 2; w++) {
Integer[] t = box(38, 27, 43, 3, 9, 82, 10);
check(run(w, t, nat) == 11, "trace inversions");
check(Arrays.equals(t, box(3, 9, 10, 27, 38, 43, 82)), "trace sorted");
for (int k = 0; k < cases.length; k++) {
Integer[] b = box(cases[k]);
Integer[] expected = box(cases[k]);
Arrays.sort(expected);
check(run(w, b, nat) == invs[k], "inversions case " + k);
check(Arrays.equals(b, expected), "sorted case " + k);
}
Rec[] recs = {new Rec(4, 'a'), new Rec(2, 'b'), new Rec(4, 'c'), new Rec(1, 'd'), new Rec(2, 'e')};
run(w, recs, byKey);
check(Arrays.equals(recs, new Rec[]{new Rec(1, 'd'), new Rec(2, 'b'), new Rec(2, 'e'),
new Rec(4, 'a'), new Rec(4, 'c')}), "stable");
}
Random rng = new Random(7);
for (int t = 0; t < 300; t++) {
int n = rng.nextInt(41);
Rec[] data = new Rec[n];
Integer[] keys = new Integer[n];
for (int i = 0; i < n; i++) {
data[i] = new Rec(rng.nextInt(10), (char) ('A' + i));
keys[i] = data[i].key();
}
Rec[] expected = data.clone();
Arrays.sort(expected, byKey); // stable TimSort
for (int w = 0; w < 2; w++) {
Rec[] b = data.clone();
run(w, b, byKey);
check(Arrays.equals(b, expected), "random stable sort");
check(run(w, keys.clone(), nat) == inversionsNaive(keys), "random inversions");
}
}
System.out.println("ok");
}
}
#include <algorithm>
#include <cstddef>
#include <functional>
#include <iostream>
#include <random>
#include <vector>
// comp(x, y) is a strict "x before y". Merges a[lo..mid) and a[mid..hi) via aux.
template <class T, class Comp>
long long mergeRuns(std::vector<T>& a, std::vector<T>& aux, std::size_t lo, std::size_t mid,
std::size_t hi, Comp comp) {
std::copy(a.begin() + lo, a.begin() + hi, aux.begin() + lo);
std::size_t i = lo, j = mid;
long long inv = 0;
for (std::size_t k = lo; k < hi; ++k) {
if (i < mid && (j >= hi || !comp(aux[j], aux[i]))) { // aux[i] <= aux[j]: ties go left
a[k] = aux[i++];
} else {
a[k] = aux[j++];
inv += static_cast<long long>(mid - i);
}
}
return inv;
}
template <class T, class Comp>
long long sortRange(std::vector<T>& a, std::vector<T>& aux, std::size_t lo, std::size_t hi, Comp comp) {
if (hi - lo <= 1) return 0;
std::size_t mid = lo + (hi - lo) / 2;
long long inv = sortRange(a, aux, lo, mid, comp) + sortRange(a, aux, mid, hi, comp);
if (!comp(a[mid], a[mid - 1])) return inv; // already in order
return inv + mergeRuns(a, aux, lo, mid, hi, comp);
}
template <class T, class Comp = std::less<T>>
long long mergeSort(std::vector<T>& a, Comp comp = Comp{}) {
std::vector<T> aux(a);
return sortRange(a, aux, 0, a.size(), comp);
}
template <class T, class Comp = std::less<T>>
long long mergeSortBottomUp(std::vector<T>& a, Comp comp = Comp{}) {
const std::size_t n = a.size();
std::vector<T> aux(a);
long long inv = 0;
for (std::size_t width = 1; width < n; width *= 2)
for (std::size_t lo = 0; lo + width < n; lo += 2 * width)
inv += mergeRuns(a, aux, lo, lo + width, std::min(lo + 2 * width, n), comp);
return inv;
}
long long inversionsNaive(const std::vector<int>& a) {
long long c = 0;
for (std::size_t i = 0; i < a.size(); ++i)
for (std::size_t j = i + 1; j < a.size(); ++j)
if (a[i] > a[j]) ++c;
return c;
}
struct Rec {
int key;
char tag;
bool operator==(const Rec&) const = default;
};
template <class T, class Comp = std::less<T>>
long long run(int which, std::vector<T>& a, Comp comp = Comp{}) {
return which == 0 ? mergeSort(a, comp) : mergeSortBottomUp(a, comp);
}
int fail(const char* msg) {
std::cerr << msg << "\n";
return 1;
}
int main() {
auto byKey = [](const Rec& x, const Rec& y) { return x.key < y.key; };
std::vector<std::vector<int>> cases{{}, {1}, {2, 2, 2}, {5, 2, 4, 6, 1, 3}, {8, 7, 6, 5, 4, 3, 2, 1},
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}};
std::vector<long long> invs{0, 0, 0, 9, 28, 0};
for (int w = 0; w < 2; ++w) {
std::vector<int> t{38, 27, 43, 3, 9, 82, 10};
if (run(w, t) != 11 || t != std::vector<int>{3, 9, 10, 27, 38, 43, 82}) return fail("trace");
for (std::size_t k = 0; k < cases.size(); ++k) {
auto b = cases[k];
auto expected = cases[k];
std::sort(expected.begin(), expected.end());
if (run(w, b) != invs[k] || b != expected) return fail("case");
}
std::vector<Rec> recs{{4, 'a'}, {2, 'b'}, {4, 'c'}, {1, 'd'}, {2, 'e'}};
run(w, recs, byKey);
if (recs != std::vector<Rec>{{1, 'd'}, {2, 'b'}, {2, 'e'}, {4, 'a'}, {4, 'c'}}) return fail("stable");
}
std::mt19937 rng(7);
for (int t = 0; t < 300; ++t) {
int n = static_cast<int>(rng() % 41);
std::vector<Rec> data;
std::vector<int> keys;
for (int i = 0; i < n; ++i) {
data.push_back({static_cast<int>(rng() % 10), static_cast<char>('A' + i)});
keys.push_back(data.back().key);
}
auto expected = data;
std::stable_sort(expected.begin(), expected.end(), byKey);
for (int w = 0; w < 2; ++w) {
auto b = data;
run(w, b, byKey);
if (b != expected) return fail("random stable sort");
auto k = keys;
if (run(w, k) != inversionsNaive(keys)) return fail("random inversions");
}
}
std::cout << "ok\n";
return 0;
}
type Cmp<T> = (x: T, y: T) => number;
// Merge sorted a[lo..mid) and a[mid..hi) via aux. Returns the cross inversions.
function merge<T>(a: T[], aux: T[], lo: number, mid: number, hi: number, c: Cmp<T>): number {
for (let k = lo; k < hi; k++) aux[k] = a[k];
let i = lo;
let j = mid;
let inv = 0;
for (let k = lo; k < hi; k++) {
if (i < mid && (j >= hi || c(aux[i], aux[j]) <= 0)) { // ties go left: stable
a[k] = aux[i++];
} else {
a[k] = aux[j++];
inv += mid - i;
}
}
return inv;
}
function mergeSort<T>(a: T[], c: Cmp<T>): number {
const aux = a.slice();
const sort = (lo: number, hi: number): number => {
if (hi - lo <= 1) return 0;
const mid = (lo + hi) >>> 1;
const inv = sort(lo, mid) + sort(mid, hi);
if (c(a[mid - 1], a[mid]) <= 0) return inv; // already in order
return inv + merge(a, aux, lo, mid, hi, c);
};
return sort(0, a.length);
}
function mergeSortBottomUp<T>(a: T[], c: Cmp<T>): number {
const n = a.length;
const aux = a.slice();
let inv = 0;
for (let width = 1; width < n; width *= 2) {
for (let lo = 0; lo < n - width; lo += 2 * width) {
inv += merge(a, aux, lo, lo + width, Math.min(lo + 2 * width, n), c);
}
}
return inv;
}
function inversionsNaive(a: number[]): number {
let cnt = 0;
for (let i = 0; i < a.length; i++) for (let j = i + 1; j < a.length; j++) if (a[i] > a[j]) cnt++;
return cnt;
}
function check(ok: boolean, msg: string): void {
if (!ok) throw new Error(msg);
}
const num: Cmp<number> = (x, y) => x - y;
type Rec = [number, string];
const byKey: Cmp<Rec> = (x, y) => x[0] - y[0];
const same = (x: unknown, y: unknown): boolean => JSON.stringify(x) === JSON.stringify(y);
for (const sort of [mergeSort, mergeSortBottomUp]) {
const t = [38, 27, 43, 3, 9, 82, 10];
check(sort(t, num) === 11 && same(t, [3, 9, 10, 27, 38, 43, 82]), "trace");
const cases: Array<[number[], number]> = [
[[], 0], [[1], 0], [[2, 2, 2], 0], [[5, 2, 4, 6, 1, 3], 9], [[8, 7, 6, 5, 4, 3, 2, 1], 28],
[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 0],
];
for (const [data, inv] of cases) {
const b = [...data];
check(sort(b, num) === inv && same(b, [...data].sort(num)), `${sort.name} on ${data}`);
}
const recs: Rec[] = [[4, "a"], [2, "b"], [4, "c"], [1, "d"], [2, "e"]];
sort(recs, byKey);
check(same(recs, [[1, "d"], [2, "b"], [2, "e"], [4, "a"], [4, "c"]]), "stable");
}
let seed = 7;
const rand = (m: number): number => {
seed = (seed * 1103515245 + 12345) % 2147483648;
return seed % m;
};
for (let t = 0; t < 300; t++) {
const n = rand(41);
const data: Rec[] = [];
for (let i = 0; i < n; i++) data.push([rand(10), String.fromCharCode(65 + i)]);
const keys = data.map((r) => r[0]);
const expected = [...data].sort(byKey); // stable since ES2019
for (const sort of [mergeSort, mergeSortBottomUp]) {
const b = [...data];
sort(b, byKey);
check(same(b, expected), "random stable sort");
check(sort([...keys], num) === inversionsNaive(keys), "random inversions");
}
}
console.log("ok");
Three details the tests pin down. The bottom-up loop runs lo only while lo + width < n, so a trailing block with no partner is skipped rather than "merged" with an empty run. The skip-merge check compares a[mid-1] with a[mid] using the same <= as the merge, so equal boundary elements count as in order (no inversion) — consistent with the counter. And the inversion counter is a 64-bit integer: can have about inversions, which overflows 32 bits.
Variant: insertion sort below a cutoff
# fragment — the hybrid base case, shown for the idea only
CUTOFF = 16
def sort(lo, hi):
if hi - lo <= CUTOFF:
insertion_sort_range(a, lo, hi) # stable, fast on tiny ranges
return
mid = (lo + hi) // 2
sort(lo, mid)
sort(mid, hi)
if a[mid - 1] > a[mid]:
merge(a, aux, lo, mid, hi)
Below a few dozen elements, recursion and copying cost more than insertion sort's quadratic work. Java's legacy merge sort for objects used a cutoff of 7; Timsort uses binary insertion sort to build runs of 32–64. The exact cutoff is an implementation detail found by benchmarking. Insertion sort is stable, so the hybrid stays stable. If you count inversions, have the insertion sort return its shift count — by the theorem in the previous lesson, that is the inversion count of the small range.
Real-world uses
Language standard libraries. Timsort — a natural, run-adaptive merge sort with galloping merges — is the stable sort in CPython (list.sort, sorted), in Java for object arrays and Collections.sort, in V8 (Chrome, Node.js) for Array.prototype.sort, and in Android. Rust's stable slice::sort has always been merge-based (Timsort-like, and since Rust 1.81 a newer design called driftsort). C++ std::stable_sort is a merge sort with a temporary buffer, degrading to when no buffer can be allocated. Perl has used merge sort for sort since 5.8. The reason is the same everywhere: these sorts must be stable and must not have a quadratic worst case on adversarial input.
Linked lists in systems code. The Linux kernel's list_sort (lib/list_sort.c) is a bottom-up merge sort on its intrusive doubly linked lists, written to use extra space and to keep merges balanced for cache behaviour; callers across the kernel, including several filesystems, use it. std::list::sort and std::forward_list::sort in C++ are merge sorts for the same reason — a list has no random access, so quicksort's partitioning and heap sort's indexing do not apply.
External sorting in databases. When a query's ORDER BY, GROUP BY, DISTINCT, index build or merge join needs to sort more rows than fit in its memory budget, the database writes sorted runs to disk and merges them. PostgreSQL reports this in EXPLAIN ANALYZE as Sort Method: external merge Disk: …kB once a sort exceeds work_mem. The merge join itself is a two-way merge of sorted inputs. See How Databases Work, Query Planning & Optimization and, for the full algorithm, Sorting in the Real World.
LSM-tree compaction. Log-structured merge trees — the storage engine of RocksDB, LevelDB, Cassandra and many others — keep data in immutable sorted files (SSTables) and periodically compact them by merging several sorted files into one, dropping overwritten and deleted keys. A compaction is a -way merge. Storage Engines and Build a Key-Value Store show it in context.
Big data frameworks. MapReduce and Hadoop sort each mapper's output into runs, spill them to disk, and merge them on the reducer side ("shuffle and sort"). Spark's sort-based shuffle does the same. The GNU sort command sorts files larger than memory by writing sorted temporary files and merging them, and parallelises with --parallel.
Search and ranking. Merging sorted posting lists is the core of query evaluation in an inverted index: intersecting the document-ID lists for "merge" and "sort" is a merge that outputs only common IDs (Search Engineering). Inversion counts measure disagreement between two rankings — Kendall's tau distance is the number of inversions of one ranking relative to the other — and are computed with exactly the merge-sort counter on this page when is large.
Version control. Three-way merges in Git are not merge sort, but the underlying operation — walk two sorted sequences (of lines, of tree entries sorted by path) in lockstep — is the same two-pointer merge.
Pitfalls & edge cases
<instead of<=in the merge. Still sorts, but breaks stability and makes the inversion counter count equal pairs. Test with duplicate keys.- Midpoint overflow.
(lo + hi) / 2overflows a 32-bitintwhenlo + hiexceeds — the bug that sat in Java'sArrays.binarySearchand merge sort for nearly a decade (Joshua Bloch, 2006). Uselo + (hi - lo) / 2or(lo + hi) >>> 1in Java. - Inversion count overflow. Up to inversions: for that is about , more than a 32-bit integer holds. Use
long/long long/ Python's ints. - Allocating in every call. Creating new lists for every merge (the "slice and concatenate" style) is total allocation and is often 3–10 times slower than one shared buffer. Fine for interviews, not for production.
- Infinite recursion. Splitting
[lo, hi)atmid = (lo + hi) // 2with the base casehi - lo <= 1always makes progress. Mixing inclusive and exclusive bounds ([lo, mid]and[mid, hi]) or using a base case oflo == hiwith inclusive bounds is the classic source of stack overflows. - Bottom-up trailing block. The last block may have no partner, or a partner shorter than
width. Cliphiatnand skip blocks withmid >= n. - Counting the wrong thing in "count smaller after self". You must sort indices (or
(value, index)pairs) so that counts are credited to the original positions; sorting values loses track of whom each count belongs to. - Reverse pairs counted during the merge. The condition
a[i] > 2·a[j]is not the merge order, so it must be counted with a separate two-pointer pass before merging; folding it into the merge's comparisons gives wrong answers. Also,2·a[j]overflows 32-bit integers for values near — use 64-bit. - Recursion depth in Python. Depth is only , so the default recursion limit is no problem for merge sort itself — but a careless linked-list merge written recursively (merge two lists by recursing on the tails) has depth and will overflow. Merge lists iteratively.
Variations
- Natural merge sort. Start from the runs already present in the input instead of from single elements. On sorted input: one run, zero merges, comparisons. Timsort is natural merge sort plus a minimum run length, a stack-based merge policy and galloping.
- Galloping (exponential search) merges. When one run keeps winning, switch from one-at-a-time comparison to exponential search for how many elements in a row it will win, then copy that block. Merging runs of sizes then costs comparisons — much less than when one run is short. Used in Timsort.
- -way merge. Merge sorted sequences at once with a min-heap holding the current head of each: for total elements. Used in external sorting, LSM compaction and "merge sorted lists" (LeetCode 23). Heaps & Priority Queues covers the heap; a loser tree (tournament tree) does the same with about comparisons per element and is preferred in external sorts.
- External merge sort. Phase 1: read memory-sized chunks, sort each, write them out as runs. Phase 2: merge runs at a time, where is limited by how many input buffers fit in memory. With bytes of data and bytes of memory, phase 1 produces about runs and phase 2 needs passes; with 100 GB of data and 1 GB of memory, 100 runs merge in a single 100-way pass, so the data is read and written about twice. Replacement selection produces runs of average length on random input, halving the number of runs. Full treatment in Sorting in the Real World.
flowchart LR
IN["input file<br/>N bytes"] --> R1["run 1: sort M bytes"]
IN --> R2["run 2: sort M bytes"]
IN --> RK["run N/M"]
R1 --> H["k-way merge<br/>(heap or loser tree)"]
R2 --> H
RK --> H
H --> OUT["sorted output file"]
- Merge sort on linked lists in extra space. Bottom-up: repeatedly walk the list, cutting off two sublists of length
width, merging them by relinking, and appending the result to a tail pointer; doublewidthuntil one pass merges everything. No recursion, no buffer, time, stable. LeetCode 148 below has the code. - Parallel merge sort. The two recursive calls are independent, so they can run in parallel; with a parallel merge (split both runs by binary search around a median) the span is or better, and Cole's algorithm (1988) achieves time on processors. Java's
Arrays.parallelSortuses a parallel sort-merge on the fork/join pool. - Three-way and multiway merge sort. Splitting into parts gives with a heap merge — still , but with fewer passes over memory, which is what matters on disk and helps cache behaviour in memory.
- Block merge sort (in place, stable). WikiSort and GrailSort: time, extra memory, stable, complicated. Useful when memory is truly constrained.
- Divide and conquer beyond sorting. "Split, solve halves, combine across the split in linear time" solves closest pair of points, counting inversions, the maximum subarray (as a teaching example), and offline problems via CDQ divide and conquer. The divide-and-conquer lesson in Module 5 generalises the pattern.
Practice ladder
Easy → hard. Descriptions are paraphrased; follow the links for the exact statements.
1. Merge Sorted Array (LeetCode 88) — merge a second sorted array into the first, which has spare room at its end, in place. Teaches the merge run backwards so that nothing is overwritten before it is read.
Hint
Fill from the back: compare the last unread elements of both arrays and write the larger one into the last free slot.
2. Merge Two Sorted Lists (LeetCode 21) — splice two sorted linked lists into one. Teaches the merge by relinking with a dummy head, the building block of list merge sort.
Hint
dummy = tail = ListNode(); while both lists are non-empty, attach the smaller head to tail (ties from the first list for stability) and advance. Attach whatever remains.
3. Sort an Array (LeetCode 912) — sort integers without the built-in sort in . Teaches writing the canonical implementation from memory; note that adversarial tests make naive quicksort time out, while merge sort is safe.
Hint
The page's top-down merge_sort with one auxiliary buffer. Check that [5, 1, 1, 2, 0, 0] and an array of 50,000 equal values both work.
4. Sort List (LeetCode 148) — sort a linked list in time; the follow-up asks for extra space. Teaches bottom-up merge sort on lists.
Hint
Count the length. For width = 1, 2, 4, …: walk the list, cut two sublists of width nodes, merge them, attach to a tail pointer, continue from where you cut. A helper split(head, k) that cuts after k nodes and returns the rest keeps the code short.
Solution
class ListNode:
def __init__(self, val: int = 0, next: "ListNode | None" = None):
self.val, self.next = val, next
def split(head, k):
"""Cut the list after k nodes; return the head of the remainder."""
for _ in range(k - 1):
if head is None:
return None
head = head.next
if head is None:
return None
rest = head.next
head.next = None
return rest
def merge_lists(a, b, tail):
"""Merge a and b after tail (stable); return the new tail."""
while a and b:
if a.val <= b.val:
tail.next, a = a, a.next
else:
tail.next, b = b, b.next
tail = tail.next
tail.next = a or b
while tail.next:
tail = tail.next
return tail
def sort_list(head):
n, p = 0, head
while p:
n, p = n + 1, p.next
dummy = ListNode(0, head)
width = 1
while width < n:
cur, tail = dummy.next, dummy
while cur:
left = cur
right = split(left, width)
cur = split(right, width)
tail = merge_lists(left, right, tail)
width *= 2
return dummy.next
def build(xs):
d = t = ListNode()
for x in xs:
t.next = ListNode(x)
t = t.next
return d.next
def to_list(h):
out = []
while h:
out.append(h.val)
h = h.next
return out
import random
assert to_list(sort_list(build([4, 2, 1, 3]))) == [1, 2, 3, 4]
assert to_list(sort_list(build([-1, 5, 3, 4, 0]))) == [-1, 0, 3, 4, 5]
assert to_list(sort_list(build([]))) == []
rng = random.Random(1)
for _ in range(200):
xs = [rng.randint(-5, 5) for _ in range(rng.randint(0, 30))]
assert to_list(sort_list(build(xs))) == sorted(xs)
print("ok")
time, extra space: only a constant number of pointers, no recursion, no buffer. The tail walk at the end of merge_lists is linear in the merged length, so each pass is still .
5. Merge k Sorted Lists (LeetCode 23) — merge sorted linked lists. Teaches the -way merge: a heap of heads () or pairwise merging in rounds, which is bottom-up merge sort over lists.
Hint
Push (node.val, list_index, node) for each non-empty head into a min-heap (the index breaks ties so nodes are never compared). Pop, append, push that node's successor. Or merge lists pairwise: round 1 merges lists 0+1, 2+3, …; each round halves the number of lists.
6. Inversion Count (SPOJ INVCNT) — count inversions in arrays of up to about elements. Teaches the counter on this page, and that the answer needs 64-bit integers.
Hint
merge_sort from the canonical block already returns the count. In C++ or Java make sure the counter is 64-bit.
Solution
def count_inversions(a: list[int]) -> int:
"""Return the inversion count; sorts a copy with merge sort."""
a = list(a)
aux = [0] * len(a)
def sort(lo: int, hi: int) -> int:
if hi - lo <= 1:
return 0
mid = (lo + hi) // 2
inv = sort(lo, mid) + sort(mid, hi)
aux[lo:hi] = a[lo:hi]
i, j = lo, mid
for k in range(lo, hi):
if i < mid and (j >= hi or aux[i] <= aux[j]):
a[k] = aux[i]
i += 1
else:
a[k] = aux[j]
j += 1
inv += mid - i
return inv
return sort(0, len(a))
assert count_inversions([3, 1, 2]) == 2
assert count_inversions([2, 3, 8, 6, 1]) == 5
assert count_inversions([38, 27, 43, 3, 9, 82, 10]) == 11
assert count_inversions(list(range(1000, 0, -1))) == 1000 * 999 // 2
assert count_inversions([]) == 0
print("ok")
time, space. A Fenwick tree over compressed values (Module 3) gives the same bound and is the other standard answer.
7. Inversion Counting (Codeforces 911D) — a permutation and a sequence of segment reversals; after each reversal, report whether the number of inversions is odd or even. Teaches reasoning about inversion parity instead of recounting.
Hint
Count the initial parity once (, so even works). Reversing a segment of length flips the order of all pairs inside it and leaves every other pair alone, so the parity changes iff is odd.
8. Pair of Topics (Codeforces 1324D) — count pairs with . Teaches rewriting a pair condition as with , after which order no longer matters and sorting plus two pointers (or binary search) counts pairs in .
Hint
With the condition is symmetric in and , so you may sort . For each , count the in sorted order with by binary search. Use 64-bit for the answer.
9. Count of Smaller Numbers After Self (LeetCode 315) — for each element, count the strictly smaller elements to its right. Teaches inversion counting credited per element: sort indices, and when a left element is output, add the number of right elements already output.
Hint
Merge sort an array of indices by value. During a merge, keep moved = how many right-half indices have been output so far. When you output a left-half index p, every right element output before it is smaller and lies to its right: counts[p] += moved. Ties must go left so equal values are not counted.
Solution
def count_smaller(nums: list[int]) -> list[int]:
n = len(nums)
counts = [0] * n
idx = list(range(n))
aux = [0] * n
def sort(lo: int, hi: int) -> None:
if hi - lo <= 1:
return
mid = (lo + hi) // 2
sort(lo, mid)
sort(mid, hi)
aux[lo:hi] = idx[lo:hi]
i, j, moved = lo, mid, 0
for k in range(lo, hi):
if i < mid and (j >= hi or nums[aux[i]] <= nums[aux[j]]):
counts[aux[i]] += moved # right elements already output are smaller
idx[k] = aux[i]
i += 1
else:
idx[k] = aux[j]
j += 1
moved += 1
sort(0, n)
return counts
def brute(nums):
return [sum(1 for j in range(i + 1, len(nums)) if nums[j] < nums[i]) for i in range(len(nums))]
import random
assert count_smaller([5, 2, 6, 1]) == [2, 1, 1, 0]
assert count_smaller([-1]) == [0]
assert count_smaller([-1, -1]) == [0, 0]
rng = random.Random(3)
for _ in range(300):
xs = [rng.randint(-5, 5) for _ in range(rng.randint(0, 25))]
assert count_smaller(xs) == brute(xs)
print("ok")
time, space. Summing the output gives the inversion count — this is the same algorithm, credited per element.
10. Reverse Pairs (LeetCode 493) — count pairs with . Teaches counting a non-merge condition across the halves with a separate two-pointer pass, before merging.
Hint
After both halves are sorted, for each i in the left half advance a pointer j through the right half while a[i] > 2 * a[j]; because the left half is sorted ascending, j never moves back. Add j - mid for each i. Then merge normally.
Solution
def reverse_pairs(nums: list[int]) -> int:
a = list(nums)
aux = [0] * len(a)
def sort(lo: int, hi: int) -> int:
if hi - lo <= 1:
return 0
mid = (lo + hi) // 2
cnt = sort(lo, mid) + sort(mid, hi)
j = mid
for i in range(lo, mid): # count first: the condition is not the merge order
while j < hi and a[i] > 2 * a[j]:
j += 1
cnt += j - mid
aux[lo:hi] = a[lo:hi] # then an ordinary merge
p, q = lo, mid
for k in range(lo, hi):
if p < mid and (q >= hi or aux[p] <= aux[q]):
a[k] = aux[p]
p += 1
else:
a[k] = aux[q]
q += 1
return cnt
return sort(0, len(a))
def brute(nums):
n = len(nums)
return sum(1 for i in range(n) for j in range(i + 1, n) if nums[i] > 2 * nums[j])
import random
assert reverse_pairs([1, 3, 2, 3, 1]) == 2
assert reverse_pairs([2, 4, 3, 5, 1]) == 3
assert reverse_pairs([2147483647] * 5) == 0
rng = random.Random(5)
for _ in range(300):
xs = [rng.randint(-20, 20) for _ in range(rng.randint(0, 25))]
assert reverse_pairs(xs) == brute(xs)
print("ok")
: the counting pass is linear per merge because j only moves forward. Negative numbers are fine — the left half is still sorted, so thresholds are still monotone. In Java or C++ compute 2L * a[j] to avoid overflow.
11. Count of Range Sum (LeetCode 327) — count subarrays whose sum lies in . Teaches reducing to pairs of prefix sums -style conditions — count pairs with — and counting them across merge-sort halves with two monotone pointers.
Hint
Build prefix sums . For each left-half (sorted), the valid right-half form a contiguous window in the sorted right half; two pointers lo_ptr and hi_ptr only move forward as increases. Add hi_ptr - lo_ptr, then merge.
Solution
def count_range_sum(nums: list[int], lower: int, upper: int) -> int:
p = [0]
for x in nums:
p.append(p[-1] + x)
aux = [0] * len(p)
def sort(lo: int, hi: int) -> int:
if hi - lo <= 1:
return 0
mid = (lo + hi) // 2
cnt = sort(lo, mid) + sort(mid, hi)
a_ptr = b_ptr = mid
for i in range(lo, mid):
while a_ptr < hi and p[a_ptr] - p[i] < lower:
a_ptr += 1
while b_ptr < hi and p[b_ptr] - p[i] <= upper:
b_ptr += 1
cnt += b_ptr - a_ptr
p[lo:hi] = sorted(p[lo:hi]) # merge (sorted() on two runs is Timsort: linear here)
return cnt
return sort(0, len(p))
def brute(nums, lower, upper):
n = len(nums)
return sum(1 for i in range(n) for j in range(i, n) if lower <= sum(nums[i:j + 1]) <= upper)
import random
assert count_range_sum([-2, 5, -1], -2, 2) == 3
assert count_range_sum([0], 0, 0) == 1
rng = random.Random(9)
for _ in range(200):
xs = [rng.randint(-6, 6) for _ in range(rng.randint(1, 15))]
lo = rng.randint(-5, 3)
up = lo + rng.randint(0, 5)
assert count_range_sum(xs, lo, up) == brute(xs, lo, up)
print("ok")
time. The sorted() call on a range made of two sorted runs is a shortcut: Timsort detects the two runs and merges them in linear time, so the bound holds; in other languages write the merge.
12. String Reversal (Codeforces 1430E) — the minimum number of adjacent swaps that turn a string into its reverse. Teaches reducing to inversions: match the -th occurrence of each letter in the reversed string to the -th occurrence in the original, build the resulting permutation, count its inversions.
Hint
For each letter keep a queue of its positions in the original string. Walk the reversed string; for each letter pop the earliest unused original position — matching occurrences in order never creates an unnecessary inversion. The answer is the inversion count of the sequence of popped positions; use 64-bit.
13. Create Sorted Array through Instructions (LeetCode 1649) — insert numbers one by one; each insertion costs the smaller of (elements strictly less) and (elements strictly greater) already present; total cost modulo . Teaches computing "smaller before" and "greater before" for every element — two inversion-style counts — with merge sort or a Fenwick tree.
Hint
For each position , "less before " is a count of smaller elements to the left — the mirror image of LeetCode 315. "Greater before " = − (less or equal before ). Compute both with merge sort on indices (or a Fenwick tree over values, Module 3), then sum the minimums.
14. Number of Pairs Satisfying Inequality (LeetCode 2426) — count pairs with . Teaches the general recipe: move everything indexed by to one side and by to the other ( with ), then count across merge-sort halves with one monotone pointer.
Hint
After sorting both halves of : for each right-half , the valid left-half are those , a prefix of the sorted left half whose length only grows as grows. Count with a pointer, then merge.
Common mistakes & interview follow-ups
"Merge sort or quicksort?" Merge sort: stable, guaranteed , sequential access, natural for linked lists and external data, fewer comparisons; costs extra memory and more data movement. Quicksort: in place, usually faster on arrays of primitives because it moves less data, but unstable and in the worst case unless guarded (introsort). Libraries use quicksort variants for primitives, where stability is meaningless, and merge-based Timsort for objects.
"Can you make merge sort use extra space?" On a linked list, yes — bottom-up relinking. On an array, only with in-place merging: with rotations, or with block merge sort at a large constant. Saying "allocate one buffer of and copy only the smaller run" is the practical answer.
"What is the recursion depth?" , independent of the input. (Quicksort's depth can be without care.)
"Your inversion count is wrong for duplicates." Usually < instead of <= in the merge, which counts equal pairs as inversions.
"The data is 100 GB and you have 1 GB of RAM." External merge sort: produce 100 sorted runs of 1 GB, then one 100-way merge with a heap or loser tree, reading each run through its own buffer. Two passes over the data. Mention that sequential I/O dominates, so large buffers and fewer passes matter more than CPU.
"What if the input is a stream and you need the sorted output incrementally?" You cannot output the minimum before seeing all elements, so a full sort needs all data. If the stream consists of several sorted streams, a -way merge outputs incrementally.
"Count pairs with / / …" Same template as reverse pairs: sort halves, count across with a monotone pointer, merge. The condition must be monotone in both and for the pointer to work.
"Why not count inversions with a Fenwick tree instead?" You can: compress values, sweep left to right, query "how many seen so far are greater". Same , often simpler for online variants. Merge sort needs no extra structure and no coordinate compression, and it naturally handles the cross-half conditions (reverse pairs, range sums) that are awkward for a Fenwick tree.
Quick quiz
1. How many comparisons does merging [1, 2, 3] with [4, 5, 6] take? Merging [1, 3, 5] with [2, 4, 6]?
Answer
3 and 5. In the first, 1, 2 and 3 each beat 4, after which the left run is empty and 4, 5, 6 are copied without comparisons: . In the second the runs interleave to the end: .
2. Count the inversions of [2, 4, 1, 3, 5] and say in which merge of a top-down merge sort each is found.
Answer
Three: , , . Top-down splits into [2, 4] and [1, 3, 5]; [2, 4] has none; [1, 3, 5] splits into [1] and [3, 5] and has none. The final merge of [2, 4] with [1, 3, 5] outputs 1 while 2 and 4 wait (+2) and 3 while 4 waits (+1): all 3 are cross inversions found in the last merge.
3. Why is case 2 of the Master theorem, and what changes if the merge cost instead?
Answer
and matches it, so . With (and the regularity condition for ) it is case 3: — the root's work dominates.
4. You change <= to < in the merge. Does the output stay sorted? What else changes?
Answer
It stays sorted, but among equal keys the right half's element is output first, so the sort becomes unstable, and the inversion counter adds mid - i for equal pairs, overcounting by the number of equal pairs that straddle a split.
5. Bottom-up merge sort is run on a linked list of 1,000 nodes. How many passes, and how much extra memory?
Answer
passes (widths ), and extra memory — a handful of pointers. Each pass is , so total.
Further reading / sources
- Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed. (1998) — §5.2.4 (sorting by merging, exact counts), §5.3.1 (minimum-comparison sorting and ), §5.4 (external sorting, replacement selection, loser trees).
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS), 4th ed. — §2.3 (merge sort and its analysis), §4.3–4.5 (recursion trees and the master theorem), Problem 2-4 (inversions).
- Robert Sedgewick and Kevin Wayne, Algorithms, 4th ed. — §2.2 (mergesort, top-down and bottom-up, the cutoff and skip-merge improvements).
- Jon Kleinberg and Éva Tardos, Algorithm Design (2005) — §5.3 (counting inversions, with the ranking motivation).
- Philippe Flajolet and Mordecai Golin, "Mellin Transforms and Asymptotics: The Mergesort Recurrence", Acta Informatica 31, 1994 — the exact average and the oscillating linear term.
- Bing-Chao Huang and Michael A. Langston, "Practical In-Place Merging", Communications of the ACM 31(3), 1988.
- Tim Peters, listsort.txt — Timsort's runs, galloping and merge policy.
- Joshua Bloch, "Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken", Google Research Blog, 2006 — the midpoint overflow.
- Linux kernel source,
lib/list_sort.c— a production bottom-up linked-list merge sort. - cppreference:
std::stable_sort,std::inplace_merge— complexity with and without a buffer. - PostgreSQL documentation, Using EXPLAIN — reading
Sort Method: external merge.
Lessons: previous — Elementary Sorts & Stability · next — Quick Sort, Partition Schemes & Introsort · module — Searching & Sorting · course — DSA: Zero to Mastery.
Related Archon pages: Two Pointers · Linked Lists · Heaps & Priority Queues · Recursion & Mathematical Induction · Complexity Analysis · Sorting in the Real World · Storage Engines · Sorting & Searching (overview).