Picture a big shuffled stack of numbered cards. Sorting all of them at once feels overwhelming, so don't. Cut the stack in half, cut each half in half again, and keep cutting until every little pile holds just one card. A single card is already "sorted" — there's nothing to do. Now go the other way: take two one-card piles and lay them down smallest-first to make a sorted pair. Stitch two sorted pairs into a sorted four, then two fours into an eight, and so on until the whole stack is back together and perfectly in order. That "split all the way down, then combine back up" rhythm is merge sort.
The clever part is the combine step, called the merge. To fuse two piles that are already sorted, you only ever peek at the top card of each pile, take the smaller one, and repeat. You never dig deeper, so merging piles holding $n$ cards in total costs only about $n$ comparisons — linear, not quadratic. How many rounds of merging are there? Each round doubles the pile size, so you can only halve the problem $\log_2 n$ times. With $n = 8$ cards you split 3 times because $2^3 = 8$, giving 3 merge rounds. Multiply the two: about $n$ work per round $\times\;\log_2 n$ rounds $=\;n\log_2 n$. For $n = 16$ that is roughly $16 \times 4 = 64$ comparisons, versus $16^2 = 256$ for a naive sort — and the gap only widens as $n$ grows.
Formally, the running time obeys the recurrence $T(n) = 2\,T(n/2) + \Theta(n)$: two half-size subproblems plus one linear-time merge. The Master Theorem (Case 2) solves this to $T(n) = \Theta(n \log n)$. Crucially, this bound holds for the best, average, and worst case alike, because the merge always costs $\Theta(n)$ no matter how jumbled — or how tidy — the input already is. The price you pay for that guarantee is memory: the merge needs an $O(n)$ scratch buffer. In the sim above, the n slider sets the array size and the Preset menu (sorted, reverse, nearly, equal) sets the starting order; watch the Recursion Depth bar climb to $\log_2 n$ and the Comparisons card tick up.
First, run the Already sorted preset, note the final Comparisons count, then run Reverse sorted and compare — they stay close, proving merge sort shrugs off input order (unlike quicksort). Next, drag n from 4 up through 8, 16, 32 and watch the recursion depth rise by exactly one at each doubling ($2 \to 3 \to 4 \to 5$). Finally, switch to the Complexity Graph tab and see the $n\log n$ curve sit far below the $n^2$ curve as $n$ increases.
Merge Sort is a classic divide-and-conquer algorithm invented by John von Neumann in 1945. It recursively divides the array into two halves, sorts each half, then merges the two sorted halves. It is the canonical example of the Master Theorem Case 2 and is the basis for external sorting algorithms (sorting data too large for RAM). It is stable and guarantees \(\Theta(n \log n)\) in all cases.
| Symbol | Meaning |
|---|---|
| \(n\) | Input array size |
| \(T(n)\) | Total operations as function of n |
| \(a=2\) | Number of subproblems (two halves) |
| \(b=2\) | Subproblem size divisor (half size) |
| \(f(n)=\Theta(n)\) | Merge cost at each level |
| \(\log_2 n\) | Recursion depth |
Two recursive calls on halves + O(n) merge step.
Case 2: if \(f(n) = \Theta(n^{\log_b a})\), then \(T(n) = \Theta(n^{\log_b a} \log n)\).
At depth \(k\), there are \(2^k\) subproblems each of size \(n/2^k\). Merge cost at depth \(k\): \(2^k \cdot O(n/2^k) = O(n)\). Total depth: \(\log_2 n\). Total cost: \(O(n) \times \log_2 n = O(n \log n)\). ✓
Merge Sort makes between \(\frac{n}{2}\log_2 n\) (best, when one half exhausted before comparing) and \(n\log_2 n - n + 1\) (worst) comparisons. Both cases are \(\Theta(n \log n)\).
Unlike Quicksort, Merge Sort requires O(n) extra space for the merge step — a key disadvantage vs Heapsort.
Merge Sort is stable: when L[i] = R[j], we prefer L[i] (use ≤, not <), preserving the original order of equal elements. This is essential for multi-key sort stability (Timsort's merge phase).
Array: [38, 27, 43, 3, 9, 82, 10, 1]
Split: [38,27,43,3] | [9,82,10,1]
Recurse left: [38,27] | [43,3] → merge → [27,38] | [3,43] → merge → [3,27,38,43]
Recurse right: [9,82] | [10,1] → merge → [9,82] | [1,10] → merge → [1,9,10,82]
Final merge: [3,27,38,43] + [1,9,10,82] → compare 3 vs 1 → pick 1; 3 vs 9 → pick 3; ... → [1,3,9,10,27,38,43,82]
mid = (lo + hi) / 2 — integer overflow for large arrays.mid = lo + (hi - lo) / 2. For large arrays where lo + hi > INT_MAX (happens when lo and hi are both near 2³¹-1), the addition overflows. The corrected formula avoids overflow by computing the offset from lo. This is the same bug in classic Binary Search and is explicitly called out in Bentley's "Programming Pearls" and CLRS Problem 2.3.