Why does introsort's depth limit hand off to heapsort rather than to merge sort?

## What the depth limit is for Quicksort's average behaviour is excellent and its worst case is `O(n^2)`, reached when partitioning is repeatedly lopsided — one side gets almost everything, so the recursion is `n` levels deep instead of about `log2 n`. For most workloads this is a curiosity. For a library sort it is a liability, and for anything reachable from untrusted input it is an availability risk: an attacker who knows the split rule can craft input that drives a sort into quadratic time, turning a request that should take microseconds into one that takes minutes. Introsort's answer is deliberately blunt: **stop trusting quicksort after a fixed number of levels**. Set a budget of about `2 * floor(log2 n)` levels; decrement it on the way down; if a subrange is reached with the budget exhausted, abandon quicksort for that subrange and finish it with a sort that has a hard `O(n log n)` worst-case bound. The total is then `O(n log n)` no matter what the input is. ## Why the constant 2 A perfectly balanced split halves the range, so an ideal run needs about `log2 n` levels. Ordinary, real-world imbalance costs somewhat more than that. A budget of `2 log2 n` leaves generous headroom, so the fallback is not tripped by input that is merely a bit unlucky, while still bounding the work done in quicksort mode: the recursion can spend at most `2 log2 n` levels doing `O(n)` work each, so quicksort mode contributes `O(n log n)` even before the fallback runs. The exact multiplier is a tuning choice, not a law — what matters is that it is a constant times `log n`, which is what makes the bound come out right. ## Why heapsort and not merge sort Both heapsort and merge sort are `O(n log n)` in the worst case, so on the guarantee alone either would do. They differ on **space**: | sort | worst-case time | auxiliary space | stable | |---|---|---|---| | quicksort | `O(n^2)` | `O(log n)` stack | no | | heapsort | `O(n log n)` | `O(1)` | no | | merge sort (array form) | `O(n log n)` | `O(n)` | yes | Introsort's selling point is a sort with quicksort's speed, quicksort's memory profile, and a worst-case ceiling. Fall back to merge sort and you lose the memory profile in exactly the moment you can least afford to: a sort running on a large adversarial input suddenly asks for a buffer the size of the data. In a fixed memory budget — a game engine ordering draw calls every frame, an embedded device, a hot path that must not touch the allocator — that is not a slowdown, it is a failure mode. Heapsort rearranges the subrange in place, so the fallback needs nothing that was not already available when the sort started. The usual objection is that heapsort is slower than quicksort in practice by a meaningful constant factor. That is true and it is precisely why heapsort is the *fallback* and not the main algorithm — and why it costs almost nothing. The fallback path runs only after `2 log2 n` levels of degenerate partitioning, which realistic data does not produce. What every ordinary sort pays is one comparison and one decrement per recursive call. You are buying insurance whose premium is a few instructions per call and whose payout is bounded quadratic blowup converted into a slightly slower `O(n log n)`. ## The bound is on the whole sort, not on the fallback alone A subtlety worth stating out loud: the fallback does not sort the whole array. It sorts *the subrange whose recursion ran out of budget*. Each such subrange is handled in `O(m log m)` for its own size `m`, and the sum over all fallen-back subranges, plus the `O(n log n)` already bounded above them, is still `O(n log n)`. There is no scenario where the fallback re-does work the quicksort phase already completed. ## What the depth limit is not It is not a fix for a bad split rule — a sort that partitions poorly will simply trip the fallback more often and run at heapsort speed. It is not a stability mechanism; both quicksort and heapsort reorder equal elements, so introsort is unstable end to end. And it is not a substitute for a randomized or otherwise unpredictable split point when the concern is a deliberate attack: the depth limit bounds the *damage* from adversarial input rather than preventing the adversary from steering the algorithm. Mainstream runtimes differ on how they combine these defences — some ship a depth-limited in-place hybrid as the general-purpose sort, while others reserve their unstable in-place sort for value-like elements and route everything else to a stable merge-based sort — but the depth limit is the piece that turns "usually fast" into "never catastrophic".