Quicksort blows the stack on a year of already-ordered sensor timestamps — how do you bound its recursion depth?

### Read the failure correctly The symptom is a stack overflow; the cause is the split ratio. Sensor timestamps appended in recording order arrive already ordered, and a pivot taken from a fixed end of the range is then the smallest or largest element present. Every partition therefore yields an empty side and a side of n-1, and the recursion is a chain with one frame per record — about 525,600 frames for a year of per-minute samples, against a typical stack that holds tens of thousands. The process dies long before the quadratic comparison count would have made itself felt. Two diagnoses that miss: "the dataset got too big" (a balanced run of the same size needs 20 frames, not half a million) and "raise the stack limit" (this moves the cliff by a constant factor while the depth still grows linearly with input size — next year's data hits it again). ### The structural fix: recurse small, loop large Quicksort's second recursive call is in tail position — nothing happens after it returns. A tail call can be replaced by updating the current frame's bounds and looping. If you always eliminate the call on the *larger* side and keep the recursive call for the smaller side, you get a guarantee: > The smaller partition is at most half the range, because two parts cannot both exceed half. So each nested frame handles at most half of what its parent handled, and the depth is at most log2 n. That bound holds for *every* input, including the maximally lopsided one, because it never assumes anything about where the pivot lands — it only uses the fact that of two pieces, the smaller one cannot be the bigger half. Half a million records now need at most about 20 frames instead of half a million. The cost of the fix is one comparison of the two side lengths per partition; the comparison count and the work done are otherwise identical. ### The direction of the claim This is the point interviewers actually probe. Bounding recursion depth fixes **space**, not **time**. The same ordered input still produces ranges of sizes n, n-1, n-2, … and therefore still does O(n^2) comparisons; you have converted a crash into a run that finishes eventually. A candidate who says "recursing on the smaller side makes quicksort O(n log n)" has swapped the two axes. Time is repaired by changing *where the split lands* — which is a different lever entirely — while depth is repaired by changing *which side keeps the frame*. ### What mainstream implementations actually do Different runtimes made visibly different calls on the same problem, which is a good sign that there is no single right answer. C++ standard libraries settled on introsort, which counts recursion depth and, past a threshold of about 2·log2 n, abandons the quicksort recursion for heapsort — accepting a slower constant in exchange for a hard O(n log n) worst case with bounded depth. Java's library sorts split by data kind instead, using a dual-pivot quicksort variant for primitives and a stable merge-based sort for objects, so the object path has logarithmic depth by construction. The smaller-side trick, a depth cap with a fallback, and choosing an algorithm whose depth is structural are three answers to the same question, and a senior candidate should be able to say which one a given constraint argues for. ### Checking your reasoning at the whiteboard A quick way to convince an interviewer the bound is real: if the smaller side has size s and the range has size n, then s ≤ (n-1)/2 < n/2. Applying that at every nested frame gives sizes below n/2, n/4, n/8, so the chain of frames cannot exceed log2 n before reaching size 1. Nothing in the argument mentions the pivot, the data, or the ordering, which is exactly why the guarantee is unconditional — the same style of reasoning as merge sort's, which gets its depth bound from splitting positionally. ### The rest of the hardening conversation Bounding depth is the first move; the interviewer's follow-ups usually go to whether you would also cap depth and switch algorithms, whether you would prefer a sort whose worst case is structural when the job runs unattended overnight, and how you would have caught this before production — a test that feeds the sort a sorted range is the one that would have found it, and sorted input is not an exotic case for timestamped data, it is the normal case.