Why can quicksort's recursion depth reach O(n) while merge sort's is always O(log n)?

### Depth is a property of the split ratio, not of the algorithm's name For any divide-and-conquer recursion, the depth is how many times you can shrink the problem before hitting the base case. If every level cuts the range to a fixed fraction — a half, a third, nine tenths — the depth is logarithmic in n, because repeated multiplication by a constant fraction reaches 1 in a logarithmic number of steps. If a level removes a *constant number of elements* instead of a constant fraction, the depth is linear. That single distinction, fraction versus fixed amount, is the whole answer. ### Merge sort: the split ratio is fixed by construction Merge sort divides by computing a midpoint index. The two children are of size ceil(n/2) and floor(n/2), and no value in the array can change that. So the depth of the recursion is ceil(log2 n) for every possible input. For half a million sensor readings — a year of one-per-minute samples is about 525,600 — that is 20 nested frames. There is no input, adversarial or otherwise, that makes it 21. ### Quicksort: the split ratio is data-dependent Quicksort's boundary lands at the pivot's rank within the range. Consider the same year of timestamps, but arriving in the order they were recorded — that is, already sorted — and a pivot taken from a fixed end of the range. The pivot is then the smallest or largest element present, so the partition produces one part of size 0 and one of size n-1: ``` range of 525600 -> 0 and 525599 range of 525599 -> 0 and 525598 ... ``` Each level strips exactly one element. The recursion tree is not a tree at all; it is a chain 525,600 frames deep. This is the same degeneration a binary search tree suffers when keys are inserted in sorted order: a structure that is logarithmic when balanced becomes linear when every split is maximally lopsided. ### The claim to get the direction right on "Quicksort's recursion depth is log n" is a statement about *balanced splits*, and it is what candidates say when they have memorised the average case. The precise statements are: - **Expected depth O(log n)** — over random inputs or a randomised pivot, lopsided splits are unlikely to stack up. - **Worst-case depth O(n)** — reached on inputs whose ordering interacts badly with how the pivot is chosen. - Merge sort's depth is **O(log n) worst case**, because there is no interaction to have. And note that a merely uneven split is harmless: a guaranteed 90/10 split still gives logarithmic depth, just with a bigger constant (log base 10/9 of n). Depth blows up only when the split is lopsided by a *fixed amount* rather than a fixed ratio, level after level. ### Recursion depth is space Each pending frame holds its arguments and its return address, so depth translates directly into stack memory. This is the part candidates skip: an algorithm's space complexity includes its recursion stack. Merge sort's stack is O(log n) frames; quicksort's is O(log n) expected and O(n) worst case. On a large input, the practical failure is not a slow sort — the process runs out of stack and dies. The quadratic comparison count of the same degenerate run would take far longer to become visible than the crash does. ### What this does not say Depth and time are separate claims. A degenerate quicksort has both problems (O(n) depth *and* O(n^2) comparisons), but they can be fixed independently, and the fix for one is not the fix for the other. Likewise, big-O here is an upper bound: labelling quicksort O(n) depth in the worst case does not mean typical runs are anywhere near it — on shuffled data the depth is a small multiple of log n with overwhelming probability. ### The interviewer's real target The question is a probe for whether you understand that quicksort's recursion *shape* is decided by the data while merge sort's is decided by arithmetic. Candidates who answer "both are log n because they both halve the input" have memorised the balanced case and never asked what guarantees the halving.