Why can quicksort's recursion depth reach O(n), and how do you cap it at O(log n)?

## The incident A nightly job sorts a few million rows in memory and has done so for a year. One morning it dies immediately with a stack exhaustion, not a timeout. Nothing in the sorting code changed. What changed is upstream: another team added an ordering step to the stage that feeds it, so rows now arrive already sorted by the very key this job sorts on. The sort uses a fixed first-element pivot. Every partition picks the minimum of its range, every split is `1 : m-1`, and the recursion nests once per row. That is the double failure worth internalising: degenerate splits cost `O(n^2)` **time** and `O(n)` **stack**, and the stack limit is usually hit long before anyone notices the time. The job did not get slow — it stopped existing. ## Recursion depth is space "In-place" is a statement about **auxiliary data structures**: quicksort rearranges elements within the range and needs no buffer proportional to `n`, unlike schemes that merge into a second array. It is not a statement about total memory. Every pending recursive call holds a frame — the range bounds, the pivot index, a return address — and those frames are live memory that grows with depth. So quicksort's space complexity is `O(depth)`: - Balanced splits: depth `~ log2 n`, so `O(log n)` space. For a few million elements that is around 20 frames — nothing. - Degenerate splits: depth `~ n`, so `O(n)` space. For a few million elements that is millions of frames, and the stack is a fixed, comparatively small region. It runs out. This is the general rule, not a quicksort quirk: **for any recursive algorithm, the stack is part of its space complexity**, and a candidate who reports space without counting depth has reported the wrong number. ## The structural fix After partitioning, you hold two subranges. The insight is that you do not need a recursive call for both. Recursion in the *tail* position can be turned into a loop by reassigning the range bounds and going round again, which consumes no frame at all. And you get to choose **which** side is the loop. ``` while lo < hi: p = partition(a, lo, hi) if the left side is smaller: recurse on the left; then set lo = p + 1 // continue with the right else: recurse on the right; then set hi = p - 1 // continue with the left ``` Always recurse into the **smaller** side. Now every frame that is actually pushed covers a range of at most half its parent's size, because the smaller of two pieces of an `m`-element range is at most `m/2`. Halving from `n` can happen at most `log2 n` times, so **depth <= log2 n regardless of how badly the pivot behaves**. The pathological `1 : m-1` split now pushes a frame for a one-element range and loops on the rest — the deep chain of frames simply never forms. ## What the fix does and does not buy - **It bounds space, not time.** A first-element pivot on ordered input still does `O(n^2)` comparisons. You converted a crash into a slowdown; you did not make the sort fast. Anyone who offers this as the cure for the quadratic worst case has confused the two axes. - **It costs nothing.** One size comparison per partition, and fewer calls than before on every input, balanced or not. - **It is unconditional.** It does not rely on the pivot being good, on the data being unordered, or on any distributional assumption. That property — a hard guarantee rather than a probabilistic one — is what makes it the right first move on a shared sorting routine, where you cannot see who will feed it what. - **The order matters, and only in one direction.** Recursing into the *larger* side and looping on the smaller inverts the argument: the pushed frame can cover `m-1` elements, and the depth is back to `O(n)`. Writing the comparison backwards silently removes the entire guarantee, which makes this a detail worth a review comment. ## How the failure presents in production A time blowup shows up as a latency graph bending upward, a task overrunning its window, a queue growing — you get warning, and you can profile a running process. A depth blowup shows up as an immediate crash with a stack trace thousands of frames deep, all of them the same function. That trace is the tell: an enormous run of identical frames means unbounded recursion depth, and for a sort it means the partitions degenerated. The two questions worth asking next are what the input's ordering looks like now versus before, and whether the pivot rule reads a fixed position. ## Framing the answer Say four things and you have covered it: recursion depth is space; degenerate partitions make it `O(n)`; recursing into the smaller half and looping on the other caps it at `log2 n` for any pivot; and that bound is on space only, so the time worst case still needs a separate answer.