Quicksort's own Pitfalls and
heap sort's both mention this by name without
building it: introsort (introspective sort) is the hybrid behind C++'s
std::sort. It runs quicksort by default, but watches its own recursion depth as it
goes — if depth blows past a bound that signals a bad pivot pattern, it abandons quicksort for
that range only and finishes it with heap sort instead, whose worst case can't get any
worse no matter how adversarial the input is. Below some small range size it switches to
insertion sort for a different reason entirely: not safety, just speed on tiny ranges where
recursion overhead costs more than a few shifts. Three algorithms, one name, each covered
standalone elsewhere on this site — this page is where they're stitched together.
Enter a comma-separated array and an insertion threshold (ranges at or below
this size finish with insertion sort instead of recursing further), then step through. The
depth limit is computed automatically as 2 · floor(log2(n)) and
shown below the controls — that's the real formula introsort uses, not a simplified stand-in.
Bars use the same coloring as this site's quicksort and heap sort pages: dashed box is the active
range, solid accent is the current pivot or heap root, shaded region is confirmed-smaller during
a partition. Watch the log for a line starting "depth limit hit" — that's the
safety net actually firing, not just being described. The default array (already ascending) is
exactly the input that makes a plain last-element-pivot quicksort recurse to depth 15; paste it
into quicksort's own demo to see that happen unchecked,
then come back here and watch this page cut it off at depth 8 instead.
Quicksort's worst case needs two things at once: a bad pivot rule and enough
recursion depth to pay for it. A depth counter can't fix the first — it can't tell a good
partition from a bad one directly — but it can cap the damage from the second: quicksort's
average recursion depth is O(log n), so any range still recursing past
2 · floor(log2(n)) levels is, empirically, on the losing side of a run of lopsided
splits. Introsort doesn't try to detect why that happened; it just stops trusting
quicksort for that range and calls heap sort on it directly, which finishes any range in
O(k log k) no matter how it got there. The two fallbacks target different failure
modes and never interact: the depth check answers "is this range's partitioning history
suspicious," and the size check answers "is this range too small for recursion to be worth it,"
independent of how it was reached.
Depth is passed down as a budget that halves-in-spirit each level (decremented by one on both recursive calls, so an even split burns it the same as a lopsided one) — when it hits zero, whatever range remains gets handed to heap sort instead of another partition:
function introSort(arr) {
const n = arr.length;
if (n <= 1) return arr;
const depthLimit = 2 * Math.floor(Math.log2(n));
recurse(arr, 0, n - 1, depthLimit, 4);
return arr;
}
function recurse(arr, lo, hi, depth, threshold) {
const size = hi - lo + 1;
if (size <= 1) return;
if (size <= threshold) {
insertionSort(arr, lo, hi);
return;
}
if (depth === 0) {
heapSortRange(arr, lo, hi);
return;
}
const p = partition(arr, lo, hi);
recurse(arr, lo, p - 1, depth - 1, threshold);
recurse(arr, p + 1, hi, depth - 1, threshold);
}
function partition(arr, lo, hi) {
const pivot = arr[hi];
let i = lo - 1;
for (let j = lo; j < hi; j++) {
if (arr[j] < pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]];
return i + 1;
}
function insertionSort(arr, lo, hi) {
for (let i = lo + 1; i <= hi; i++) {
const key = arr[i];
let j = i - 1;
while (j >= lo && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
function heapSortRange(arr, lo, hi) {
const size = hi - lo + 1;
const siftDown = (i, end) => {
while (true) {
let largest = i;
const l = lo + 2 * (i - lo) + 1;
const r = lo + 2 * (i - lo) + 2;
if (l <= end && arr[l] > arr[largest]) largest = l;
if (r <= end && arr[r] > arr[largest]) largest = r;
if (largest === i) return;
[arr[i], arr[largest]] = [arr[largest], arr[i]];
i = largest;
}
};
for (let i = lo + Math.floor(size / 2) - 1; i >= lo; i--) siftDown(i, hi);
for (let end = hi; end > lo; end--) {
[arr[lo], arr[end]] = [arr[end], arr[lo]];
siftDown(lo, end - 1);
}
}Partition, insertion sort, and heap sort here are the identical schemes this site's own
quicksort,
insertion sort, and
heap sort pages already cover
in full — the only new code here is recurse's two guard checks and
heapSortRange's index math, which offsets every heap position by lo so
it can run on an arbitrary slice of the array in place, not just a whole array starting at 0.
The depth counter must be a real budget, not a fixed cutoff. A common
mistake is checking recursion depth against a constant (say, always switch after depth 40) rather
than 2 · floor(log2(n)). A constant either fires too early on small arrays — capping
a range that would've finished quicksort in a handful of levels anyway, throwing away the cache
advantage for nothing — or too late on huge ones, letting an adversarial input do far more damage
before the net catches it. Scaling the limit with n keeps the guarantee meaningful at
every size: verified directly by running the reference implementation above on sizes 50 through
1,600 with a deliberately adversarial (ascending) input at a fixed insertion threshold of 4 — the
heap sort fallback fires exactly once per run at every size, always on a range whose size matches
n − depthLimit, confirming the switch triggers precisely when the running depth
counter reaches zero rather than at some size-independent point.
The safety net is rare by design, and testing only random input will never exercise
it. The same reference implementation run 1,000 times (seeded, reproducible) on shuffled
permutations of the same 16-element array (threshold 4) triggered the heap sort fallback zero
times across all 1,000 runs, while the insertion sort fallback fired 3,385 times (small
ranges are common at every size; a depth-limit breach on random data is not, and this sample never
hit one at all). A test suite that only checks
random arrays can ship a broken depth counter — an off-by-one in the comparison, or comparing
against the wrong variable — and never notice, because the branch it broke almost never runs
against random input. It has to be exercised directly, with an adversarial input built to trigger
it, the way quicksort's own Pitfalls already
does with 1,2,3,4,5,6,7,8.
Heap sort's index math breaks if you forget the offset. Plain
heap sort assumes the heap
starts at index 0, so a child of i lives at 2i+1 and
2i+2. Running it on a sub-range [lo..hi] instead of the whole array
means every index has to be measured relative to lo first — the reference
implementation's lo + 2 * (i - lo) + 1 rather than a bare 2 * i + 1. Use
the un-offset formula on any range where lo > 0 and sift-down reads and swaps
outside the intended slice, silently corrupting whatever the finished left partition already
placed there. The default (ascending) demo array doesn't expose this — its one heap fallback
happens to land on range [0..7], where lo is already 0 and the offset
is a no-op either way. The descending version of the same array does: reverse the
default input and the fallback instead fires on [4..11]. Confirmed by deliberately
reintroducing the bug on exactly that input: the un-offset version returns
1,2,3,4,11,10,9,8,5,6,7,12,13,14,15,16 instead of fully sorted — no crash, no error,
just a wrong answer with four elements permuted inside the one range the bug corrupted.
It's still not stable. All three ingredients — quicksort's partition, heap sort's swaps, insertion sort's shifts on non-adjacent equal keys — can each reorder equal elements relative to each other, same as quicksort and heap sort alone. Combining three unstable sorts never produces a stable one.
Time: O(n log n) worst case, guaranteed — not just typical. Any
range that would push quicksort into its own O(n²) worst case gets capped at depth
2 log n and handed to heap sort's unconditional O(k log k) instead,
so the total work across every range is bounded the same way heap sort's own bound is (see
heap sort's Complexity). Average
case is quicksort's own average, unchanged, because the fallback essentially never
fires on non-adversarial input (see Pitfalls). Space: O(log n) for
the recursion stack, same as plain quicksort — heap sort and insertion sort both run in place on
whatever range they're handed, no extra allocation.
For how this fits against the other ten comparison sorts on this site — including when the guarantee this page builds actually matters over quicksort's plain average-case speed — see Choosing a Comparison Sort.