Where the cleverness goes
The previous guide gave us the divide / conquer / combine template and warned that one of the three steps usually carries the whole algorithm. Merge sort is the cleanest illustration of that warning. Its divide step is almost insultingly trivial — cut the array of n items in half by index, with no thought at all — and its conquer step is just two recursive calls on the halves. All of the design effort, and all of the running time, lives in the combine step: weaving two already-sorted halves into one sorted whole.
Contrast this with quicksort, the subject of the next guide, which does the opposite trade. Quicksort works hard to divide cleverly (partitioning around a pivot) so that its combine step is free — once the parts are sorted in place, nothing remains to do. Merge sort makes the symmetric bet: trivial divide, expensive combine. Seeing the two side by side is the real lesson, because it shows that 'divide and conquer' is not one algorithm but a budget you can spend on whichever step you choose. The merge is where merge sort decides to spend.
The merge, traced by hand
Picture two sorted piles face-up on a table, smallest card on top of each. To merge them you compare only the two top cards, move the smaller one onto the output pile, and repeat. Because each pile is already sorted, the smallest card you have not yet placed is always one of those two tops — never anything buried below — so a single comparison at the front is enough to choose correctly. When one pile empties, the other is already sorted, so you sweep its remainder onto the output untouched. That is the entire idea of merge sort's merge.
- Set two reading fingers, i at the front of the left half L and j at the front of the right half R, and an empty output list.
- While both halves still have cards: compare L[i] with R[j]; copy the smaller into the output and advance only that half's finger. Ties can go either way (keep left first to stay stable).
- When one half runs out, copy all remaining cards of the other half straight to the output — they are already in order.
- The output now holds all n items in sorted order; each item was copied exactly once.
Why is the result correct, not just plausible? Hold a loop invariant: at the top of each step the output list contains, in sorted order, exactly the items that are smaller than both current fronts L[i] and R[j]. It is true at the start (output empty). Each step preserves it: we append the smaller of the two fronts, which is the smallest unplaced item anywhere, so it correctly extends the sorted prefix. When the loop ends both halves are exhausted, so by the invariant the output is the full sorted merge. Correctness comes from that argument, not from the picture looking tidy.
Counting the merge
How expensive is one merge of two halves totalling n items? Each comparison sends exactly one item to the output, and we never look at an item twice, so the number of comparisons is at most n - 1 and the total work — comparisons plus copies — is Theta(n). That is the key fact: merging is linear in the combined size. It also explains a hidden cost people forget. The merge cannot easily be done in place; it writes into a separate output buffer, so merge sort needs O(n) extra scratch memory. The speed is bought partly with space.
Now stack the whole algorithm into a recurrence. Sorting n items costs two recursive sorts of size n/2, plus one linear merge: this is the canonical divide-and-conquer recurrence T(n) = 2 T(n/2) + O(n), with T(1) = O(1) as the base case. Almost every fast divide-and-conquer sort or search produces a relative of this equation, so learning to read it is worth more than memorizing merge sort's answer.
T(n) = 2 T(n/2) + c*n # 2 subproblems of half size, linear merge
level subproblems merge work each row total
0 1 c*n c*n
1 2 c*n/2 c*n
2 4 c*n/4 c*n
... ... ... ...
log n n c c*n
---------------
rows = log n + 1, each c*n -> total = c*n*(log n + 1) = O(n log n)The recursion-tree method makes the answer almost visible. At depth 0 there is one problem of size n; at depth 1, two of size n/2; at depth k, 2^k problems of size n/2^k. The merge work at any single level is (number of pieces) times (size of each) = 2^k times n/2^k = n, so every level costs the same Theta(n). The halving stops after about log2(n) levels, when pieces reach size 1. Multiply work-per-level by number-of-levels: Theta(n) times Theta(log n) = Theta(n log n). The master theorem confirms this instantly — with a=2, b=2, the per-level cost matches n exactly, which is its tie case — but the tree shows you why, not just that.
Same n log n, every time
A quietly remarkable property: merge sort runs in Theta(n log n) on every input — already sorted, reverse sorted, or shuffled. The split is by index, so the shape of the recursion tree never depends on the data, and the merge always does its linear pass. So merge sort's worst case, best case, and average case all coincide. That is a genuine advantage over quicksort, whose expected time is O(n log n) but whose worst case is O(n^2) on an unlucky input. With merge sort there is no unlucky input — predictability is part of what you are buying.
The merge has a charming side gig. If, each time you copy an item from the right half ahead of items still waiting in the left half, you add the count of those waiting left items, the running total is the number of inversions — pairs that are out of order — in the original array. Merge sort therefore counts inversions in O(n log n) for free, far better than the obvious O(n^2) check of all pairs. It is a small but honest demonstration that the combine step is not just bookkeeping; the work you do while merging can compute something genuinely new.
Could any comparison sort be faster?
It is natural to hope some cleverer comparison sort beats n log n. Remarkably, none can — and the reason is a clean counting argument, not a failure of imagination. Any sort that orders items only by comparing pairs can be drawn as a decision tree: each internal node asks 'is a < b?' and branches two ways, and each leaf is one final ordering the algorithm can output. To sort n distinct items correctly, the tree must have at least one reachable leaf for every possible answer, and there are n! possible orderings.
A binary tree of height h has at most 2^h leaves, so we need 2^h >= n!, which gives h >= log2(n!). By a standard estimate log2(n!) is Theta(n log n), so the tree's height — the worst-case number of comparisons — is Omega(n log n). The height is the length of the longest root-to-leaf path, i.e. the most comparisons some input forces, so this is a true lower bound on worst-case comparisons for the entire class of comparison sorts. Merge sort meets it. That makes its O(n log n) not merely good but asymptotically optimal among comparison-based methods.