Introsort: Bounding Quicksort with a Depth Counter and a Heap

Quicksort’s average case is excellent and its worst case is quadratic. The standard library cannot ship a sort whose worst case is quadratic on adversarial input, and it also cannot ship one that is consistently slower than quicksort. Introsort resolves the conflict by running quicksort and watching how deep the recursion goes; when the depth exceeds a budget, it abandons quicksort for a method with a guaranteed bound. The result is quicksort’s constants on ordinary input and heapsort’s guarantee on pathological input.

The depth budget

The budget is derived from the depth a perfectly balanced quicksort would reach. For $n$ elements the balanced depth is $\lfloor \log_2 n \rfloor$, and a factor of two is allowed for slack: the limit is $2 \lfloor \log_2 n \rfloor$.

The choice is not arbitrary. A partition that splits the range in the ratio $\epsilon : 1-\epsilon$ produces recursion depth $\log_{1/\epsilon} n$, so a depth limit of $2 \log_2 n$ is satisfied by any split up to about a $0.71$ to $0.29$ ratio, and an even worse split overshoots it. The budget therefore allows a fairly lopsided sequence but not an arbitrarily bad one. Beyond that, the guarantee is the trivial one: the subproblems at any single depth partition a subset of the array, so each level costs at most $n$ comparisons, and $2 \log_2 n$ levels cost $O(n \log n)$ in total no matter how the splits fall. What the budget forbids is unbounded depth, which is exactly what a hostile input produces when every partition splits off a single element and the level cost stays at $n$ for $n$ levels.

The counter is decremented once per partition, and the current value is passed to both the recursive call and the loop, so the budget applies to every root-to-leaf path independently. What it bounds is the length of the longest chain of partitions, not the total number of partitions performed; a sort that does many shallow partitions is unaffected. When a path exhausts its budget, the range at the end of that path is handed to heapsort and the recursion there stops. Because the recursion always takes the smaller side, the number of live budget values is bounded by the stack depth, so the counter costs nothing beyond an integer per frame.

static void introsort_loop(int *a, size_t lo, size_t hi, int depth)
{
    while (hi - lo > INSERTION_THRESHOLD) {
        if (depth-- == 0) {                 /* budget exhausted: guaranteed bound */
            heapsort_range(a + lo, hi - lo);
            return;
        }
        size_t p = partition(a, lo, hi);    /* median-of-three pivot */
        /* recurse on the smaller side, iterate on the larger: stack stays O(log n) */
        if (p - lo < hi - p) {
            introsort_loop(a, lo, p, depth);
            lo = p + 1;
        } else {
            introsort_loop(a, p + 1, hi, depth);
            hi = p;
        }
    }
}

partition is the ordinary two-index scheme and heapsort_range is an in-place heapsort over the given subrange. Two details in the fragment carry weight. The recursion is on the smaller side and the loop continues on the larger, which bounds the stack at $O(\log n)$ independent of the budget; the depth counter is what bounds time. Without that smaller-side rule a bad split sequence could exhaust the stack before the counter ran out, because every partition would add a frame instead of returning into the loop.

The base case is a size threshold rather than a single element. Ranges at or below the threshold are left unsorted by the recursion and finished by one insertion sort pass over the whole array. Since each element is within the threshold distance of its final position, that pass is linear in the number of elements plus the number of inversions, and the inversions are bounded by $n$ times the threshold.

Why heapsort and not merge sort

Merge sort also has an $n \log n$ guarantee, and its comparison count is lower than heapsort’s. It is rejected as the fallback for one reason: it needs a buffer of $\Theta(n)$ elements, and the fallback must be usable at arbitrary recursion depth inside a function that has already allocated its stack. A sort that allocates $n$ elements on the bad path can fail in exactly the situation where the caller needs it most. The standard library sort is therefore specified to reuse only the storage it is given, and allocating a shadow array inside the sort is not an option.

Heapsort needs $O(1)$ extra space, has no allocation, and its worst case is $n \log n$ comparisons and $n \log n$ moves. Its weakness is locality: sift-down jumps between a node and its children at exponentially separated indices, so each level of the heap is a cache miss on a large array. That weakness is acceptable in a fallback that runs rarely and is unacceptable in the main path, which is precisely the trade introsort makes.

There is a second reason. Heapsort’s first phase, building the heap bottom-up, is linear, and its second phase performs $n$ sift-downs of decreasing length. Once the budget is exhausted, the remaining ranges are often already partly ordered by the quicksort levels above them, and heapsort does not benefit from that ordering at all. Merge sort would, through natural runs. The cost of losing that benefit is bounded and paid only on adversarial input, so it is the right thing to give up.

The partition quality question

Introsort does not by itself fix bad pivots; it detects them. Improving pivot selection reduces how often the budget is spent. Median-of-three, described in quicksort partition schemes, handles sorted and reverse-sorted inputs. Sampling more elements and taking the median of the sample reduces the variance further at a cost of a few comparisons per partition.

The budget and the pivot rule interact. A strong pivot rule spends the budget rarely, so the fallback’s poor constants almost never apply. A weak pivot rule spends it often, and the sort’s performance approaches heapsort’s on exactly the inputs the rule handles badly. Because each root-to-leaf path carries its own copy of the counter, one badly split region does not consume budget that another region needs, and a rule that splits well almost everywhere keeps the fallback confined to the pathological part of the input.

What the guarantee actually covers

Introsort’s worst case is $O(n \log n)$ comparisons. That statement holds for any input and any comparator satisfying the contract in comparator strict weak ordering, because the fallback’s bound is unconditional and the quicksort phase’s work is bounded by the depth limit times the work per level.

The guarantee does not cover moves. Heapsort’s sift-down performs up to $\log n$ moves per extraction, so the fallback’s move count is $O(n \log n)$ but with a larger constant than quicksort’s swaps. On a pathological input the sort can therefore be correct, within its comparison bound, and still slower than a merge sort on the same input by a factor that reflects the extra moves.

Nor does the guarantee make the sort stable. Partitioning is unstable and heapsort is unstable, so introsort is unstable on every path. Callers needing stability use a merge-based sort regardless of the worst-case question, since merge sort’s worst case is already $n \log n$ and its stability comes free from the tie rule.

The general shape of the technique

Introsort is one instance of a pattern: run the fast algorithm with a monitor, and switch to the safe algorithm when the monitor fires. The monitor must be cheap, must be a reliable proxy for the bad case, and must fire early enough that the remaining work is bounded.

Other instances of the same pattern appear throughout algorithm engineering. A hash table that monitors collision counts and converts a long bucket chain to a balanced tree when it exceeds a threshold keeps average-case constant time with a logarithmic worst case. A string matcher that monitors verification failures and switches from a filter to a full comparison keeps linear expected time with a bounded worst case. In each case the guarantee comes from the fallback, and the performance comes from the fallback rarely running.

The pattern’s weakness is also shared: the two algorithms have different constants, so the combined algorithm’s performance is discontinuous in the input. Once the budget is exhausted inside a subrange, that subrange is sorted by the fallback regardless of how nearly sorted it already was, and the work attributable to it jumps from a few partition passes to a full heapsort. Introsort on an input that just barely exceeds the budget therefore does noticeably more work than one that just barely stays within it. That is acceptable for a library sort and matters for a system with a latency budget.