Recursion depth against the 2 log₂ n limit

Recursion depth against the 2 log₂ n limit

The dashed line is the depth at which introsort abandons quicksort and calls heapsort. On ordinary input the recursion barely approaches it: random input reaches depth 28 of 28 at n = 16,384, and where the fallback does fire it handles at most 0.000% of the elements. Against an adversary that answers the comparisons rather than choosing the array, the depth sits on the limit at every size, and the fallback fires. The mechanism is dead code on everything anybody sorts and it is not optional.

Drawn at 700 × 430, wide on the page. Everything above is what depth-and-fallback returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

2 essays call depth-and-fallback. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.