Algorithms and data structures · Intermediate

Introsort: guard quicksort with a depth budget

Combine quicksort partitions with a depth-triggered heapsort fallback and small-range insertion sorting.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Combine a fast partitioner with a guarantee
  2. Follow repeatedly unbalanced partitions
  3. Why the depth budget bounds work
  4. Separate properties from library choices
  5. Ask Logeia about this articleCheck your understanding

Combine a fast partitioner with a guarantee

Introsort starts with quicksort-style partitioning and changes to heapsort when a subproblem exhausts a recursion-depth budget. A typical initial budget is around twice the integer part of log₂n, although coefficients and small-range handling are implementation choices. The trigger examines the structure of the computation rather than measuring elapsed wall-clock time. Implementations also commonly finish small ranges with insertion sort. That cutoff serves a different purpose from the depth limit: one reduces overhead on tiny ranges, while the other prevents an extended sequence of damaging partitions.

Follow repeatedly unbalanced partitions

For an illustrative input size of sixteen and a budget of eight, imagine partitions that finalize only one element at a time. Remaining sizes fall slowly through fifteen, fourteen and thirteen. Continuing this behavior indefinitely creates a quadratic sum of partition scans. When the budget reaches its limit, sorting the remaining range with heapsort stops that chain. The fallback applies to unfinished subproblems, rather than restarting the entire original array. The numbers in this example explain the mechanism; they do not specify the exact threshold that every production library must use.

Why the depth budget bounds work

At one partition depth, unfinished subranges are disjoint and their lengths sum to at most n. Limiting the number of such levels to O(log n) bounds partition work by O(n log n). Heapsorting all remaining ranges also costs at most O(n log n) in total. This argument assumes linear-time partitioning and constant-time comparisons. Monitoring depth does not repair a comparator that violates ordering rules, nor does it prevent arithmetic errors in index calculations. The guarantee describes asymptotic work under the algorithm’s assumptions, not an input-independent execution time or a promise that no allocations occur.

Separate properties from library choices

Ordinary introsort is unstable because its partition and heap exchanges can reorder equal keys. Recursing on the smaller partition and iterating over the larger one can help control stack usage. A standard library’s worst-case comparison requirement is not the same as a promise that every version uses one exact introsort implementation. Pivot sampling, duplicate-key handling and insertion cutoffs can vary. When making performance claims, name the relevant implementation and environment. Test sorted, reversed and duplicate-heavy arrays to examine both correctness and behavior near the depth and small-range boundaries.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 10

Choose a learning path