Glossary: Data Structures and Algorithms in C++

Introsort

Also written: quicksort, heap sort

The algorithm behind std::sort: a quicksort that switches to heap sort if it recurses too deep, and to insertion sort on short ranges. It is O(n log n) even in the worst case but not stable. Quicksort and heap sort are other O(n log n) methods.