Why is merge sort O(n log n) on every input, including data that arrives already sorted?
answer
- the split never looks at the values
- count the work level by level
- how many halvings until runs of one?
- each level merges all n elements once
- per-level cost times number of levels
basics
~20 sMerge sort always halves the input until single-element runs remain, then merges back up. That gives about log2 n levels, and every level moves all n elements once, so the total is n log n whatever the input order.
solid answer
~50 sMerge sort splits at the midpoint, which is a positional decision that never looks at the values, so the shape of the recursion is identical for sorted, reversed and random input. That fixes the depth at `ceil(log2 n)` levels. At each level the runs of that level together contain all n elements, and merging them costs one pass over those elements — at most `n - 1` comparisons and exactly n moves. Multiply per-level cost by number of levels and you get `O(n log n)`, which is simultaneously the best case, the average case and the worst case. That guarantee is the whole selling point: there is no input an adversary can hand you that degrades it. The flip side is that plain merge sort is not adaptive — it does not get faster on nearly ordered data unless you add an explicit check.
go deeper
Be ready to say the two moving parts out loud: about log2 n levels of halving, and one full pass over all n elements at each level. Then state that the bound holds for best, average and worst case.
Explain why the split cannot be influenced by the data, and walk the recursion tree showing each level sums to n. Distinguish the fixed move count from the comparison count that does vary with input order.
Show when you would pay for this guarantee: a worst-case bound is what you cite when a latency budget must hold for the slowest request, not the median one. Be ready to name what the guarantee costs in space.
Own the argument that a predictable worst case can be worth a slower average. Explain to a team why an unbounded tail on adversarial or pathological input is a different kind of risk from a slightly higher mean cost.
## The claim Merge sort runs in `Theta(n log n)` time on every input of size n. Not "O(n log n) on average" and not "O(n log n) unless you are unlucky" — the same bound above and below, for sorted input, reversed input, all-duplicates input and random input alike. ## Why the input cannot change the shape Merge sort has two phases per call: 1. **Split.** Choose the midpoint `mid = (lo + hi) / 2` and recurse on the two halves. This is arithmetic on indices. No element value is examined. 2. **Merge.** Walk the two sorted runs with two cursors, repeatedly copying the smaller head into the output. Because the split is positional, the recursion tree is fully determined by n alone. Contrast this with a sort that partitions around a chosen element: there the partition point depends on the data, which is exactly how such an algorithm can end up with lopsided subproblems on adversarial input. Merge sort has no such lever, so it has no bad input. ## Counting the work, level by level The cost obeys `T(n) = 2*T(n/2) + O(n)`: two subproblems of half the size, plus a linear merge. The clean way to read that is as a recursion tree, counting work per level rather than per call. | Level | Number of runs | Size of each run | Merge work at this level | |---|---|---|---| | 0 (root) | 1 | n | ~n | | 1 | 2 | n/2 | 2 * n/2 = ~n | | 2 | 4 | n/4 | 4 * n/4 = ~n | | … | … | … | ~n | | last | n | 1 | ~n | The key observation is that the runs at any one level are disjoint and together cover the whole array, so their sizes sum to n. Merging is linear in the number of elements it touches, so **every level costs about n**, no matter how far down you are. The only remaining question is how many levels there are: how many times can you halve n before reaching 1? That is `ceil(log2 n)` — 10 halvings for a thousand elements, 20 for a million, 30 for a billion. Total: `n` per level times `log2 n` levels = `Theta(n log n)`. The base of the logarithm is a constant factor, not a complexity class. Splitting three ways instead of two would give `log3 n` levels but more comparison work per level; the product stays in the same class. ## Comparisons versus moves A merge of two runs holding m elements total performs exactly m moves into the output and at most `m - 1` comparisons — after one run is exhausted the tail of the other is copied with no comparisons at all. So the comparison count varies a little with the data (sorted input exhausts one run early at each merge), while the move count is rigidly n per level. This is why measured runtimes on sorted input are somewhat faster than on random input even though the asymptotic bound does not move. It is a constant-factor effect, not a change of class. ## "But surely sorted input is faster?" Only if you teach the algorithm to notice. The standard trick is one extra comparison per merge: if the last element of the left run is less than or equal to the first element of the right run, the two runs are already in order relative to each other and the merge reduces to a copy. That does not change the worst case, but it makes already-sorted input finish in `Theta(n)` after the recursion has descended. Adaptive variants go much further and detect naturally occurring ordered runs in the input, starting the merging from those instead of from single elements; on data that is already ordered they finish in linear time, and this is precisely why several mainstream standard-library sorts are built on such a variant. ## What the guarantee buys and costs The guarantee is the reason merge sort is the safe default when a latency budget must hold for the worst request, not just the median one: no input, adversarial or otherwise, pushes it to quadratic behaviour. What you pay for it is linear auxiliary space for the merge buffer, plus a recursion depth of `O(log n)` frames. ## The wrong answers to avoid - "It is `O(n)` on sorted input" — not for the textbook algorithm; the splits and merges happen regardless. - "Its worst case is quadratic like other divide-and-conquer sorts" — it has no quadratic case at all. - "The log comes from the merge" — the merge is linear; the log is the number of halvings. - Counting work per recursive call and getting lost — count per level, where each level is n.
- Does merge sort ever finish early when the input is already in order?The textbook version does not — the recursion still descends and every merge still walks both runs. One extra comparison fixes that: if the last element of the left run is not greater than the first element of the right run, the merge is just a copy. Adaptive variants go further and detect existing ordered runs in the input, which makes sorted data linear.
- Where does the level count come from when n is not a power of two?The depth is `ceil(log2 n)`: halving 1000 gives 500, 250, 125, 63, 32, 16, 8, 4, 2, 1 — ten levels. Some runs at the bottom levels are one element shorter than their siblings, which changes constants and nothing else. The bound is unaffected.
- Is the number of comparisons the same as the number of element moves?No. Each level performs exactly n moves into the output, but at most `n - 1` comparisons, because once one run is exhausted the remainder of the other is copied without comparing. On nearly ordered data one run tends to exhaust early, so comparisons drop while moves stay fixed.
Picture the recursion as a stack of about log2 n rows of index cards. Every row holds the same n cards, just grouped differently, and each row costs one full pass over them.
saying these in an interview costs you the question
- Says merge sort is linear on already-sorted input
- Claims merge sort has a quadratic worst case
- Thinks the log factor comes from the merge step
- Counts work per recursive call instead of per level
- Says the logarithm base changes the complexity class