Two sorted halves can be merged in one pass. So split the array, sort each half the same way, and merge. Watch where the sorting really happens.
Splitting, then merging back
Ten numbers sorted by halves
static void merge_halves(int *a, int *tmp, int lo, int mid, int hi){ int i = lo, j = mid, k = lo; while (i < mid && j < hi) { comparisons++; if (a[i] <= a[j]) tmp[k++] = a[i++]; else tmp[k++] = a[j++]; } while (i < mid) tmp[k++] = a[i++]; while (j < hi) tmp[k++] = a[j++]; for (k = lo; k < hi; k++) a[k] = tmp[k];} static void sort_range(int *a, int *tmp, int lo, int hi){ if (hi - lo < 2) return; int mid = lo + (hi - lo) / 2; sort_range(a, tmp, lo, mid); sort_range(a, tmp, mid, hi); merge_halves(a, tmp, lo, mid, hi);}main has started: a has room for ten ints.
- calls
- 0
- comparisons
- 0
Output
Describe this picture
Three pictures stacked, with the code beside them, the line about to run marked. At the top, a tree of calls to sort_range, one circle per call, labelled with its range: 0–10 at the root, 0–5 and 5–10 under it, down to single cells such as 0–1 and 1–2. Below it, the ten cells of int a[10] as bars: 6 2 9 1 5 10 3 8 4 7. At the bottom, the buffer tmp, ten places on the heap, drawn dashed until the program allocates it. The clip takes about 37 seconds. The tree grows depth first, the running call ringed, splitting down to single cells. When a call merges, its two halves in a are tinted in two colours, with the fingers i and j under their front values. Each comparison tints the two front bars; the smaller is copied into tmp at the marker k, and its finger moves on. When one half runs out, the rest of the other is copied. Then the merged run is copied back into a, tinted, sorted: 2 6, then 1 5, then 1 5 9, then 1 2 5 6 9, and on the right 3 4 7 8 10, until the last merge of all ten. At the end tmp greys, freed. Under the picture are one sentence on the current step and the readouts “calls” and “comparisons”, which end at 19 and 25. The transport plays and pauses, steps one beat back or forward, and scrubs; a paused step is kept in the page address as merge-sort.step.
The merges do the sorting
A range of one value is sorted. Two sorted ranges side by side can be merged into one sorted range in a single pass, as in Merging and set operations: compare their front values, take the smaller, repeat. Merge sort uses only those two facts. It splits the array in half, sorts each half by the same method, and merges them.
The splitting compares nothing. It only decides which ranges will be merged. All 25 comparisons on the house array happen in the merges, on the way back up the tree.
The code and its cost
static void merge_halves(int *a, int *tmp, int lo, int mid, int hi)
{
int i = lo, j = mid, k = lo;
while (i < mid && j < hi) {
comparisons++;
if (a[i] <= a[j])
tmp[k++] = a[i++];
else
tmp[k++] = a[j++];
}
while (i < mid)
tmp[k++] = a[i++];
while (j < hi)
tmp[k++] = a[j++];
for (k = lo; k < hi; k++)
a[k] = tmp[k];
}
static void sort_range(int *a, int *tmp, int lo, int hi)
{
if (hi - lo < 2)
return;
int mid = lo + (hi - lo) / 2;
sort_range(a, tmp, lo, mid);
sort_range(a, tmp, mid, hi);
merge_halves(a, tmp, lo, mid, hi);
}sort_range sorts the half-open range [lo, hi): a[lo] up to a[hi − 1]. merge_halves merges [lo, mid) and [mid, hi) into the same cells of tmp, then copies them back. merge_sort allocates tmp once, for n ints, calls sort_range(a, tmp, 0, n) and frees it.
The house array
The splits run [0, 10) into [0, 5) and [5, 10); [0, 5) into [0, 2) and [2, 5), then [2, 5) into [2, 3) and [3, 5); the right side the same way. The merges and their comparisons:
| Merge | Result | Comparisons |
|---|---|---|
| 6 with 2 | 2 6 | 1 |
| 1 with 5 | 1 5 | 1 |
| 9 with 1 5 | 1 5 9 | 2 |
| 2 6 with 1 5 9 | 1 2 5 6 9 | 4 |
| 10 with 3 | 3 10 | 1 |
| 4 with 7 | 4 7 | 1 |
| 8 with 4 7 | 4 7 8 | 2 |
| 3 10 with 4 7 8 | 3 4 7 8 10 | 4 |
| 1 2 5 6 9 with 3 4 7 8 10 | all ten | 9 |
merge-sort.c prints 25 comparisons.
Why n log₂ n
Merging m values makes at most m − 1 comparisons, since each comparison places one value and the last value needs none. Draw the calls as a tree: the merges on one level of the tree cover every value once between them, so a level costs at most n comparisons. Halving reaches single values after about log₂ n levels. So the whole sort makes at most about n log₂ n comparisons.
The same count comes from the recurrence. If T(n) is the cost for n values, sorting two halves and merging costs T(n) = 2T(n/2) + n. Unrolling it: 2T(n/2) + n = 4T(n/4) + 2n = … = n·T(1) + n log₂ n after log₂ n halvings, which is O(n log n). Unlike quicksort’s, this holds for every input: the splits never depend on the values.
Bottom up
The recursion only decides the order of the merges. Merging runs of width 1, then 2, then 4, … from left to right does the same work with two loops and no recursion. bottom-up.c does that with the same merge_halves:
width 1: 2 6 1 9 5 10 3 8 4 7
width 2: 1 2 6 9 3 5 8 10 4 7
width 4: 1 2 3 5 6 8 9 10 4 7
width 8: 1 2 3 4 5 6 7 8 9 10
25 comparisonsIts runs are not the recursive version’s (it pairs [0, 8) with [8, 10) at the end), and on these values it happens to make 25 comparisons too.
Properties
Merge sort is stable: a[i] <= a[j] takes the left value on a tie, so equal values keep their order. It is not in place: it needs n extra cells for tmp. Its O(n log n) holds in the best, average and worst case, so it is not adaptive either. On a linked list it needs no buffer, since merging lists only relinks nodes (Merging sorted lists).
Worked example
A thousand and twenty-four values. With n = 1,024 there are log₂ 1,024 = 10 levels, each costing at most 1,024 comparisons: at most 10,240. Insertion sort on random input averages about n²/4 ≈ 262,000.
The most a merge can cost. The last merge, 1 2 5 6 9 with 3 4 7 8 10, takes 9 comparisons, the most possible for two halves of 5. A merge stops comparing as soon as one half runs out, and here the two largest values, 9 and 10, sit in different halves, so neither half runs out before the last value.
The same idea in signal processing. The fast Fourier transform splits a signal into halves, transforms each and combines them in one pass, with the same recurrence T(n) = 2T(n/2) + n (The FFT).
Two checks. How many levels of splitting for n = 16? (4.) Why <= and not <? (So that on a tie the left value goes first: stability.)
Where it’s used
Library sorts that must be stable, often as a hybrid that finishes short runs with insertion sort.
Linked lists, which merge sort handles with no extra memory.
Files too large for memory. External sorting sorts chunks that fit, writes them out as runs, and merges the runs from disk.
Reference card
| Code or idea | Meaning |
|---|---|
sort_range(a, tmp, lo, hi) | sort [lo, hi): split at mid, sort both halves, merge |
merge_halves | merge [lo, mid) and [mid, hi) through tmp |
| merging m values | at most m − 1 comparisons |
| T(n) = 2T(n/2) + n | O(n log n), every case |
| bottom up | runs of width 1, 2, 4, …; no recursion |
| extra memory | n cells (none for linked lists) |
| in place, stable, adaptive | no, yes, no |
Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.