What Algorithm Does C++ std::sort Use?
C++'s std::sort is renowned for speed, and the reason is the clever hybrid algorithm behind it: Introsort. Here is exactly what runs when you call it and how it guarantees good performance on every input.
Introsort under the hood
Introsort begins with Quick Sort for speed, monitors recursion depth, and switches to Heap Sort if it gets too deep — guaranteeing O(n log n) and avoiding Quick Sort's O(n²) worst case. Small partitions are finished with Insertion Sort. The standard only requires O(n log n); most implementations deliver it via Introsort.
std::sort vs std::stable_sort
std::sort is not stable. If you need to preserve the order of equal elements, use std::stable_sort, which is Merge Sort based and uses O(n) memory (falling back gracefully if memory is unavailable). More in sorting algorithms in C++.
Frequently asked questions
What algorithm does C++ std::sort use? +
Is std::sort stable? +
See it in motion
Watch this algorithm and 9 others run step by step in our free interactive visualizer.
▶ Launch Visualiser