The depth limit that almost never fires

Quicksort is fast and has a quadratic worst case. Heapsort is slower and does not. Musser’s observation in 1997 was that a program can have the first algorithm’s speed and the second one’s guarantee, for the price of an integer.

Count the recursion depth. If it exceeds $2\log_2 n$, quicksort has been partitioning badly for long enough that something systematic is happening, so stop and finish this subarray with heapsort. Quicksort’s expected depth is about $1.4\log_2 n$, so on ordinary input the limit is never approached; on the input where it is, the switch caps the total at $O(n \log n)$ unconditionally.

That is introsort, it is what std::sort has been for a quarter of a century, and the interesting question about it is not whether it works. It is what a mechanism that never runs is worth, and answering that requires making it run.

How rarely it fires #

On random input at $n = 8{,}192$, averaged over eight seeds, the fallback fires twice and handles 39 elements out of 65,536 — 0.06%. At $n = 16{,}384$ it fires twice and handles 42 out of 131,072, which is 0.03%. At $n = 4{,}096$ and $n = 32{,}768$, across the same eight seeds, it does not fire at all.

Those firings are real and they are not what the mechanism is for. A subarray of forty elements can go deep by chance — the depth limit is a global budget spent by the whole recursion, so a small subarray reached after twenty levels of ordinary partitioning has almost no budget left, and finishing it with heapsort costs nothing because it is forty elements.

So the honest statement is not “the limit never fires”. It is: the limit fires occasionally, on subarrays too small for the choice to matter, and it never once handles a meaningful share of the work. That is a stronger statement than “never”, it is checkable, and it is what the gate checks — the first version of that assertion demanded zero firings and passed only because none of the eight sampled sizes happened to be one where it fires.

The figure that would show the limit firing on ordinary input cannot be drawn, and the reason is instructive. depth-and-fallback asserts that on random input the fallback handles under one per cent of the elements, and at a depth factor of 1 or 1.5 that assertion fails — because at those settings the fallback really does start handling a meaningful share of an ordinary sort. The figure refuses to draw rather than quietly showing a picture whose caption would be false.

That refusal is the measurement. The depth factor at which introsort stops being quicksort with a safety net and starts being a hybrid is somewhere between 1.5 and 2, and the shipped 2 is just past it.

Making it fire #

An adversary is needed, and the adversaries this site has used so far will not do.

The adversary who hides the edge chooses a graph. The adversary who knows the seed chooses an array, having read the algorithm’s random seed. Both choose an input in advance, and both are defeated by an algorithm that shuffles first or reseeds.

McIlroy’s killer adversary, from 1999, is different in kind. It does not choose an input. It answers the questions.

A comparison sort is defined as one that learns about its input only through comparisons. So hand it an array of distinct placeholders and supply the comparison function. Each time it asks about two elements whose values have not been decided, decide one of them — pin it to the next-smallest value available — and leave the other floating. An element that is still floating always compares greater than one that has been pinned.

The effect is that whatever the algorithm chooses as a pivot turns out to be the largest element it has seen so far. Every partition puts one element on one side and everything else on the other. Three lines of comparator, and no knowledge of the algorithm beyond the fact that it is a comparison sort.

What it costs #

With the limit removed, the adversary produces exactly half of $n^2$ comparisons, converging on 0.500 as $n$ grows, and drives the recursion to depth 4,088 out of 8,192 — one element removed per level, all the way down.

With the limit in place, the recursion reaches depth 26 out of a limit of 26, the fallback fires once, and heapsort finishes the whole remaining array. The cost is 399,927 comparisons: three times what the same algorithm spends on random input, and a factor of forty-two less than the unlimited version.

The saving grows with $n$ because the difference is $\Theta(n^2)$ against $\Theta(n \log n)$. At a million elements it would be a factor of five thousand. A mechanism that handles 0.06% of the elements on ordinary input is worth an arbitrarily large factor on the input it exists for, which is the entire argument for having it and is not an argument that can be made by measuring ordinary input.

Why the adversary works, in one sentence per line #

The rule is short enough to state in full, and each clause does one thing.

Every element starts undecided. The sort is handed the integers 0 to n−1, which are labels rather than values; the comparator never looks at them except as identities.

Comparing two undecided elements pins one of them. Whichever of the two was not the candidate gets the next-smallest unused value, and is from then on a settled, small element. So the first comparison of a partition scan settles something at the bottom of the eventual order.

An undecided element compares greater than a settled one. So anything the algorithm is holding on to — a pivot, a candidate median — floats upward as the run proceeds.

The most recently seen undecided element becomes the candidate. This is the clause that does the damage: it tracks whatever the algorithm is currently treating as special, and keeps it undecided, so that it ends up above everything it is compared against.

The result is that the pivot is always the maximum of the subarray. A partition against the maximum puts $k-1$ elements on one side and none on the other, and the recursion removes one element per level. That is $\sum k = n^2/2$ comparisons, and the measurement above lands on 0.500 of $n^2/2$ at $n = 8{,}192$ — not approximately, exactly what the argument predicts.

The adversary has to be checked, and this is how #

An oracle that answered arbitrarily could make any algorithm look terrible and would have proved nothing, because no array would produce those answers. An inconsistent comparator is not an input; it is a broken function.

So the adversary records what it settled on. After the run, the values it pinned are collected into an ordinary array, and the same algorithm is run again against that array with no adversary present.

The comparison counts are identical. 36,829 against 36,829 at $n = 1{,}024$; 183,053 against 183,053 at $n = 4{,}096$. They can only be identical if the adversary’s answers were the answers of a real total order all along — which means the adversary did not invent an impossible input, it found one, and the array it found is sitting in memory afterwards and can be handed to anything else.

That is assertTheAdversaryIsARealArray, it runs on every build, and it is the difference between a demonstration and a quotation.

And the array it found does not transfer #

Handing that array to a different median-of-three quicksort — the one in lib/algorithms.js, which has been on this site since the foundation — costs 2,665 comparisons at n = 256, against the adversary’s 6,773 against introsort. It is an ordinary input for it. Not a bad one; slightly better than random.

This is the most important limitation of the technique and it is worth stating loudly. The killer adversary is built against an implementation, not against an algorithm. It watches the specific sequence of comparisons the specific code makes, and it constructs an array that is bad for that sequence. A different pivot rule, a different partition scheme, even a different order of the two recursive calls, and the array is ordinary again.

McIlroy’s paper says exactly this and it is easy to read past. The consequence is that there is no “the quicksort killer input”; there is one per implementation, and generating it requires running the implementation. Which in turn means that an attacker who wants to trigger the quadratic case in a real program needs the program’s exact sorting code — a much stronger requirement than knowing that it uses quicksort, and a much weaker one than being unable to attack it at all.

What the limit costs when it is not needed #

The other half of the question. Introsort at depth factor 2 on random input takes 134,880 comparisons; at depth factor 3, where the fallback never fires at all, it takes 134,688. The difference is 0.14%, and it is entirely the three subarrays that got finished by heapsort instead of quicksort.

So the mechanism costs almost nothing and is worth a factor of forty-two on the input it exists for. That is an unusually clean answer for this site, and it is worth contrasting with the other three thresholds in the threshold somebody chose, none of which came out this way. minrun and the insertion cutoff are compromises between counters that pull in opposite directions; the depth limit is not a compromise at all in the region where it is set.

The one place it is not clean is duplicates. On eight distinct values, a depth factor of 0.5 costs 97,106 comparisons and the shipped 2 costs 243,350 — a factor of 2.5 in favour of giving up on quicksort much sooner. That is not the depth limit failing; it is the depth limit being asked to solve a problem it is not for, because introsort’s partition puts every element equal to the pivot on one side and there is no depth limit low enough to make that efficient. The answer is a different partition, which is the pattern that defeats the pattern.

The shipped value is on a plateau, not at an edge #

Somewhere between 1.5 and 2, and the shipped 2 is just past it reads as a knife-edge, and the arithmetic in this essay says the opposite: there is a cliff below and a plateau above, and 2 is at the bottom of the plateau.

The cliff first. Quicksort’s expected depth is about $1.4\log_2 n$, so a limit at $d\log_2 n$ leaves a margin of $d/1.4$. At $d = 2$ that is a 43% margin and the fallback handles 0.06% of the elements; at $d = 1.5$ it is 7%, which is inside the ordinary fluctuation of a random recursion, and the figure’s own assertion fails because the fallback starts handling more than one element in a hundred. One half-step of $d$ moves the fallback’s share by more than sixteen times.

Now above. Ordinary input costs 134,880 comparisons at $d = 2$ and 134,688 at $d = 3$ — the higher limit is 0.14% cheaper, because three subarrays that were finished by heapsort get finished by quicksort instead.

And the adversary’s side is estimable from the mechanism. It removes one element per level, so reaching depth $L$ costs about $Ln - L^2/2$ before the switch, plus a heapsort on what is left. At $n = 8{,}192$: $L = 26$ gives roughly 213,000 plus about 106,000, against a measured 399,927 — the right shape and a third low, which is the partition scan’s own constant. At $L = 39$ the first term is about 319,000, so $d = 3$ costs the adversary about a quarter more than $d = 2$.

Put the two together and the objective is flat. Between $d = 2$ and $d = 3$ the ordinary case improves by 0.14% and the worst case degrades by 26% — both small, neither decisive, and any value in that range is defensible. Below 1.5 the ordinary case falls off a cliff and the choice becomes forced.

Which is a better account of why this constant has survived twenty-nine years unchanged than it is just past the threshold. A constant sitting on a plateau needs no retuning, because nothing measurable moves when it does — and that is a different kind of stability from the compromises in the threshold somebody chose, where every value trades one counter against another and moving it always costs something. Here the shipped value is the cheapest point of a flat region, which is where a constant nobody will revisit ought to be put. Expected is not average is why the margin has to be there at all: the depth is a distribution, and 43% is the room its upper tail needs.

The stack, which is the other reason #

There is a second argument for the depth limit that has nothing to do with comparisons, and this site has an essay about it already.

Quicksort’s recursion is auxiliary space. The stack nobody counts measured it: a quicksort that recurses on both sides without ordering them can reach depth $n$, and at $n = 7{,}000$ on the build machine that exhausts the interpreter’s actual stack rather than merely being slow. A quadratic-time sort is a performance problem; a sort that overflows the stack is a crash.

Against the adversary, unlimited introsort reaches depth 4,088 at $n = 8{,}192$ — half the array, one frame per two elements. With the limit it reaches 26. The C++ standard requires std::sort to work on arrays that fill memory, and a recursion depth proportional to $n$ makes that impossible whatever the time bound says.

So the depth limit is doing two jobs with one integer: capping the time and capping the space. Real implementations do a third thing as well — recurse on the smaller side and loop on the larger, which bounds the depth at $\log_2 n$ regardless — and pdqsort does exactly that. Introsort as measured here does not, which is why its peak auxiliary space at $n = 8{,}192$ is 28 slots against pdqsort’s 9.

Three mechanisms, all of them about the same failure, none of them redundant, because the depth limit bounds time and the tail-loop bounds space and neither implies the other.

It is worth being precise about what the tail-loop trick is, because it is the one piece of quicksort engineering that is pure gain. After partitioning, recurse on the smaller side and continue the loop on the larger. The smaller side is at most half the range, so each nested call at least halves the remaining size, so the depth is at most $\log_2 n$ — unconditionally, on every input, with or without a depth limit, with or without a good pivot rule.

That bound holds even when the time is quadratic. An algorithm that partitions maximally badly still has logarithmic stack depth if it loops on the large side, because the recursion only ever descends into the small one. So the two mechanisms are genuinely independent: the tail loop gives an unconditional space bound and says nothing about time, the depth limit gives an unconditional time bound and, on its own, says nothing about space.

That figure is the clearest statement of what the limit is and is not. Raising it does not make ordinary input any faster, because ordinary input never reached the old limit. It makes the adversary’s case worse in exact proportion. A guarantee is bought entirely at the expense of the case it guards against, and costs the ordinary case nothing — which is a very unusual shape for a design decision and is why this one has survived unchanged for twenty-nine years while the other three thresholds in this phase are all compromises.

The limit against three sweeps #

The depth the recursion actually reaches is a measurement, and a measurement taken once over one range is the kind of thing this essay exists to complain about.

And the range is the third thing to vary, because a depth curve against a limit that both grow like $\log n$ is a comparison of two lines whose gap is the whole subject.

A guarantee is not a prediction, and this is the clearest case #

The site’s founding theme is that an asymptotic bound describes a limit and does not predict a duration. The depth limit is the sharpest possible illustration, from an unusual direction.

Introsort’s guarantee is $O(n \log n)$ worst case, unconditionally, with no assumption about the input. Quicksort’s is $O(n \log n)$ expected, or average-case, depending on which version — and expected is not average established that those two are different claims about different things.

The three are ranked, and the ranking is entirely about what the claim survives:

• Average-case is a claim about the distribution of inputs. It evaporates the moment somebody chooses the input, and the adversary above is what choosing looks like.
• Expected-case is a claim about the algorithm’s own coins. It survives any input, and it fails if the adversary learns the seed.
• Worst-case is a claim about nothing at all. It holds against an adversary who has the source code, the seed, and unlimited time.

Introsort buys the third for 0.14% of the comparisons. The reason that is a good trade is not that quadratic behaviour is likely — it is not — but that the cost of the guarantee is bounded and known, and the cost of not having it is not.

That last figure is the essay in one picture, and it is a picture of nothing happening. Every curve sits at the logarithm; no limit is approached; the mechanism might as well not exist. Every measurement of ordinary behaviour says the same. The only way to show what it is for is to build the thing it is for, and that took an adversary that answers rather than one that chooses.