A hand-rolled introsort passes its depth counter down unchanged on one branch — what breaks?

## The invariant that the guarantee rests on Introsort's worst-case bound is an argument about the recursion tree. Start with a budget of about `2 * floor(log2 n)`; require that **every** recursive call receives a strictly smaller budget than its parent; and when the budget reaches zero, finish that subrange with an in-place, worst-case-`O(n log n)` sort. From those three facts it follows that no path can be longer than the budget, that the quicksort phase does at most `O(n)` work on each of `O(log n)` levels, and that everything below a zeroed budget is bounded by the fallback. Total: `O(n log n)`. Break the middle requirement on even one branch and the argument collapses. Consider this shape: ``` sort(a, lo, hi, depth): if hi - lo < CUTOFF: insertion_sort(a, lo, hi); return if depth == 0: heapsort(a, lo, hi); return p = partition(a, lo, hi) sort(a, lo, p - 1, depth - 1) sort(a, p + 1, hi, depth) // budget forwarded unchanged ``` Every call reachable by going right forever holds the same budget its ancestor held. The right spine of the recursion tree has no depth bound at all. ## Why this is worse than it looks The failure is not symmetric with the input. The recursion goes right when the split point lands near the low end — which is exactly the pattern degenerate input produces. So the branch left unprotected is the branch that pathological input travels. The sort will handle an adversarially or pathologically ordered array by recursing `Θ(n)` levels deep, doing `Θ(n^2)` comparison work, and quite possibly overflowing the call stack first — a crash rather than a slow response, which on a server is the more severe outcome. Meanwhile the fallback still *exists*, still passes code review by eye, and still appears in the code coverage report if any test happens to construct a small enough limit. The guarantee is entirely notional. ## Why tests miss it On random input, quicksort's recursion depth is tightly concentrated around a small multiple of `log2 n` — well under a budget of `2 log2 n`. A test suite made of random arrays, sorted arrays of a few hundred elements, and hand-written edge cases will never reach the limit on either branch. The sort produces correct output in every case, at normal speed. Nothing is red. That is the general shape of this defect class: **a safety mechanism whose absence is invisible until the day it is needed**. Correctness tests cannot find it, because the code is correct; performance tests cannot find it, because the common case is unaffected. ## How to actually verify it Three techniques, in increasing order of strength: 1. **Instrument and assert.** Expose a counter of fallback invocations (or maximum depth reached) in test builds, and assert on an input engineered to be degenerate for that implementation's split rule that the fallback fired and the observed depth stayed within the budget. 2. **Property-test the bound.** For many generated inputs, including deliberately hostile ones, assert that measured recursion depth never exceeds the initial budget. This catches the one-branch bug directly, because the bug's signature is depth exceeding the budget. 3. **Make it structurally impossible.** Compute the child budget once — `child = depth - 1` — and pass that variable to both calls, so a future editor cannot decrement one side and not the other. Better still, keep a single depth parameter and derive the fallback test from it in one place. ## Where to look when reviewing sort code The habit worth taking away: for any algorithm whose headline property is a guarantee, review **the plumbing that carries the guarantee**, not the routine that does the visible work. Reviewers' eyes go to the partition function, because that is where the clever code is and where an off-by-one would corrupt output. But partition bugs are loud — they produce wrong answers and tests catch them within minutes. The bug that survives to production is in the parameter passed down the recursion, the initial budget computed from the wrong `n` (the whole array's length versus the current subrange's), the fallback branch placed after the recursion instead of before it, or the base-case check that shadows the depth check so the limit is never consulted on short ranges. Each of those keeps the sort correct and quietly deletes its worst-case bound.