Merge Sort

Merge sort is a comparison-based, stable, divide-and-conquer sorting algorithm. Given an array $A[1..n]$, it operates in three phases characteristic of divide-and-conquer: 1. Divide: split $A$ into two contiguous halves, $A[1..\lceil n/2 \rceil]$ and $A[\lceil n/2 \rceil+1..n]$. 2. Conquer: recursively sort each half. 3. Combine: merge the two now-sorted halves into a single sorted array. The divide step is trivial — it costs constant time to compute a midpoint index. The conquer step is handled entirely by recursion; there is no cleverness there, just trust in the recursive hypothesis (this trust is exactly what the inductive correctness proof formalizes). All of the algorithm's substance lives in the merge operation: combining two sorted sequences of total length $n$ into one sorted sequence using only $\Theta(n)$ comparisons and moves, and no more than $\Theta(n)$ extra space. A sort is called stable if it preserves the relative order of elements that compare equal. Merge sort achieves stability by a simple tie-breaking rule in the merge step: when the front elements of the two halves are equal, always take the element from the left half first. Because the left half's elements originated earlier in the array, this preserves their original relative order. Stability is not a cosmetic property — it is essential when sorting records by a secondary key after already sorting them by a primary key, a common pattern in databases and spreadsheets.

The algorithm recurses on index ranges of a single array, using an auxiliary array only during the merge step (allocating it once and reusing it, or allocating per-call — both are common; the pseudocode below allocates a temporary buffer at merge time for clarity, noting the standard optimization of reusing one shared buffer).

Base case: an array of length 0 or 1 is already sorted — there is nothing to do.

Merge step: given two adjacent sorted runs $A[p..q]$ and $A[q+1..r]$, produce a single sorted run occupying $A[p..r]$. This is done by maintaining two pointers, one into each run, always copying the smaller of the two "next" elements into an output buffer, and copying it in on ties from the left run to preserve stability. When one run is exhausted, the remainder of the other run is copied directly — no more comparisons are needed since it is already sorted. ``` // Sorts A[p..r] in place, using recursion and a linear merge. MERGE-SORT(A, p, r): if p >= r: return // base case: 0 or 1 elements, already sorted q = floor((p + r) / 2) MERGE-SORT(A, p, q) // conquer left half MERGE-SORT(A, q + 1, r) // conquer right half MERGE(A, p, q, r) // combine // Merges two adjacent sorted runs A[p..q] and A[q+1..r] into one sorted run. MERGE(A, p, q, r): L = A[p..q] // copy left run R = A[q+1..r] // copy right run i = 0 // index into L j = 0 // index into R k = p // index into A, the write cursor while i < length(L) and j < length(R): if L[i] <= R[j]: // "<=" is what makes the sort stable A[k] = L[i] i = i + 1 else: A[k] = R[j] j = j + 1 k = k + 1 while i < length(L): // copy any remaining left elements A[k] = L[i] i = i + 1 k = k + 1 while j < length(R): // copy any remaining right elements A[k] = R[j] j = j + 1 k = k + 1 ``` The top-level call is `MERGE-SORT(A, 1, n)`. Note the two crucial details that a correct implementation must get right: the base case condition `p >= r` (not `p == r`, since recursive calls can produce an empty range only if misused, but more importantly the comparison must stop recursing on singletons), and the tie-break `L[i] <= R[j]` rather than `<`, which is precisely what guarantees stability. The figure below shows the recursive splitting ("divide") followed by the bottom-up merging ("combine") for an eight-element array.

Correctness (proof by strong induction on subarray length). We claim `MERGE-SORT(A, p, r)` correctly sorts $A[p..r]$ into non-decreasing order, for every valid pair $p \le r$. Base case: if $p \ge r$, the subarray has at most one element, which is trivially sorted. No work is done, correctly. Inductive step: let $n = r - p + 1 > 1$ and assume, as the inductive hypothesis, that `MERGE-SORT` correctly sorts every subarray strictly shorter than $n$. The call computes $q$ so that both $A[p..q]$ (length $\lceil n/2 \rceil$) and $A[q+1..r]$ (length $\lfloor n/2 \rfloor$) are strictly shorter than $n$. By the inductive hypothesis, the two recursive calls leave these subarrays sorted. It remains to show that `MERGE` correctly combines two sorted adjacent runs into one sorted run.

Merge correctness (loop invariant): consider the main `while` loop of `MERGE`, with indices $i, j, k$. The invariant is: > At the start of each iteration, $A[p..k-1]$ consists of the smallest $k - p$ elements of $L \cup R$ (as a multiset), placed in sorted order, and $L[i], R[j]$ are the smallest not-yet-copied elements of each run respectively. Initialization: before the first iteration, $k = p$, $i = j = 0$; $A[p..k-1]$ is empty, vacuously satisfying the invariant. Maintenance: at each step, since $L$ and $R$ are individually sorted, the smallest element not yet placed must be either $L[i]$ or $R[j]$ — no earlier element in either run remains unplaced, and no later element in either run can be smaller than its own run's front. The algorithm compares $L[i]$ and $R[j]$ and copies the smaller (or $L[i]$ on ties) into $A[k]$, extending the sorted prefix by one correctly placed element, and increments the corresponding pointer and $k$. Termination: the loop ends when $i = |L|$ or $j = |R|$. At that point every remaining element in the other run is, by the sortedness of that run, at least as large as everything already placed, so copying the rest directly (the two cleanup loops) preserves sortedness. When both cleanup loops finish, $A[p..r]$ contains all elements of $L$ and $R$ in sorted order. This establishes the inductive step, completing the induction and proving `MERGE-SORT(A, 1, n)` sorts any array of length $n$.

Stability. The tie-breaking rule `L[i] <= R[j]` always prefers the left run on equal keys. Since the left run's elements were located at smaller original indices than the right run's, and this rule is applied consistently at every level of recursion, an easy induction on recursion depth shows equal elements never have their relative order reversed.

Time complexity. `MERGE(A, p, q, r)` does $\Theta(n)$ work where $n = r - p + 1$: copying into $L, R$ is $\Theta(n)$, and the merge loop performs at most $n - 1$ comparisons and exactly $n$ writes total (each iteration of every loop writes one element, and there are $n$ writes total across all three loops). So merging is $\Theta(n)$ in the best, average, and worst case — merging never gets to skip work, unlike some other combine steps. Let $T(n)$ be the worst-case running time of `MERGE-SORT` on an array of size $n$. Then:

Assuming $n$ is a power of two for a clean derivation (the general case adds only lower-order rounding terms), this is $T(n) = 2T(n/2) + \Theta(n)$. Unrolling via a recursion tree: at recursion depth $i$, there are $2^i$ subproblems each of size $n/2^i$, each contributing $\Theta(n/2^i)$ merge work, so each full level costs $\Theta(n)$ total. The recursion has depth $\log_2 n$ (halving until reaching size 1), giving

Equivalently, by the Master Theorem with $a = 2$, $b = 2$, $f(n) = \Theta(n)$: since $f(n) = \Theta(n^{\log_b a}) = \Theta(n^1)$, we are in the "balanced" case, giving $T(n) = \Theta(n \log n)$ directly — the same recurrence machinery introduced when studying Recurrences in general. Crucially, unlike quicksort, this bound holds in the worst case, not merely on average, because the split is always exactly balanced by array position, regardless of the input's values.

Space complexity. The standard implementation uses $\Theta(n)$ auxiliary space for the merge buffers, plus $\Theta(\log n)$ stack space for recursion. Merge sort is not in-place: it is impossible to merge two sorted halves of a shared array using only $O(1)$ extra space while keeping the merge linear-time — in-place linear merging exists but is complex and typically not worth its constant-factor overhead in practice. This Θ(n) extra memory is the primary tradeoff against algorithms like quicksort or heapsort.

Honest tradeoffs summary:

Trace `MERGE-SORT` on $A = [5, 2, 4, 6, 1, 3, 2, 6]$ (indices $1..8$).

Divide phase (recursion splits down to singletons, as shown in the figure): the array splits into $[5,2,4,6]$ and $[1,3,2,6]$, each splitting again into $[5,2]$, $[4,6]$, $[1,3]$, $[2,6]$, each splitting into singletons.

Merge phase, level by level:

The final merge is worth expanding to show the tie-break rule in action, since both runs contain a `2` and a `6`:

Final sorted array: $[1, 2, 2, 3, 4, 5, 6, 6]$. Note step 2 and step 7 both show the tie-break rule choosing the left run's element first — this is exactly the mechanism that guarantees stability when the two equal `2`s or `6`s originated from records that should retain their relative input order.

Merge sort's early tie to tape-based and punch-card sorting machines is not incidental: merging is naturally suited to devices that can only read sequentially, one reason it dominated "external sorting" long before modern RAM-resident sorting became cheap.

Merge sort's guarantees make it the default choice whenever predictability and stability outweigh raw average-case speed or memory frugality. Concretely:

• External sorting: when data is too large to fit in memory (database sort-merge joins, sorting log files spanning many disk blocks), data is split into chunks that fit in memory, sorted, and then merged sequentially from disk — exactly the merge-sort pattern, since merging needs only sequential access, not random access.
• Standard library sorts for objects: Java's `Arrays.sort` for object arrays, and Python's Timsort (used in `list.sort` and `sorted`), rely on merge-sort-family algorithms specifically because sorting user-defined objects by a key must be stable to behave predictably under repeated, multi-key sorts.
• Linked lists: merge sort adapts naturally to linked lists, needing only pointer rearrangement and no random-access indexing, unlike quicksort or heapsort, which lean on array indexing or in-place swaps.
• Parallel and distributed sorting: because the two recursive halves are entirely independent, merge sort parallelizes cleanly across cores or machines (e.g., MapReduce-style shuffle-and-sort phases), with only the merge step requiring coordination.
• Inversion counting and related problems: the merge step naturally counts how many pairs are "out of order" with a small modification, a classic application taught alongside merge sort itself.

Merge sort also serves as the canonical example when introducing the Comparison-Sort Lower Bound: since it achieves Θ(n log n) comparisons, and no comparison-based sort can beat Ω(n log n) in the worst case (an information-theoretic bound from counting the $n!$ possible orderings), merge sort is asymptotically optimal among comparison sorts — a benchmark against which algorithms like Quicksort are then compared on other axes, such as space usage and average-case constants.

Ask the tutor: How would you modify the merge step to count the number of inversions in an array, and why does this run in the same Θ(n log n) time as the sort itself?