Introsort Explained
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 9 others run step by step in our free interactive visualizer.
▶ Launch Visualiser