Introsort Explained
Introsort is the hybrid algorithm behind C++ std::sort, combining Quick Sort, Heap Sort, and Insertion Sort. Learn how it guarantees O(n log n) worst case.
On this page +
Introsort (introspective sort) is the algorithm behind C++'s std::sort. It is a hybrid that starts with Quick Sort for speed, switches to Heap Sort if recursion gets too deep to avoid the O(n²) trap, and finishes small partitions with Insertion Sort. The result is Quick Sort's average performance with a guaranteed O(n log n) worst case.
Why combine three algorithms? #
Each component covers a weakness of the others. Quick Sort is fast on average but can hit O(n²). Heap Sort is guaranteed O(n log n) but slower in practice. Insertion Sort is fastest of all on tiny arrays. Introsort uses each where it is strongest.
How Introsort works #
It begins partitioning like Quick Sort while tracking recursion depth, capped at roughly 2·log₂(n). If a branch exceeds that depth — a sign Quick Sort is degenerating — it switches that partition to Heap Sort, which cannot exceed O(n log n). Once partitions shrink below a small threshold (about 16 elements), it stops recursing and runs a single Insertion Sort pass over the whole nearly-sorted array.
Complexity and significance #
Introsort is O(n log n) worst case, in-place with O(log n) stack, and not stable. It is significant because it shows how production libraries combine textbook algorithms to get the best of each — much like Tim Sort does for stable sorting.
Frequently asked questions
What algorithm does C++ std::sort use? +
How does Introsort avoid Quick Sort's worst case? +
See it in motion
Watch this algorithm and nine others run step by step, with live pseudocode and comparison counters.
Launch the visualiser Software engineer at a stealth-stage startup, and previously a front-end engineer for around a year and a half.