Why std::sort Is So Fast: The Three Algorithms and a Magic Number Behind Its Speed

The Core of std::sort

Opening stl_algo.h reveals that std::sort consists of only two effective calls: __introsort_loop and __final_insertion_sort. The first performs quicksort‑style partitioning but stops recursing when a sub‑range contains fewer than 16 elements, leaving a "half‑sorted" region for the second phase.

Why Quick‑Sort Needs a Safety Net

Quicksort is fast on average (O(n log n)) and uses far less memory than mergesort, but its performance hinges on the quality of the pivot. If the pivot is repeatedly the smallest or largest element, recursion depth degrades to O(n) and the algorithm collapses to O(n²). McIlroy (1999) proved that any deterministic pivot‑selection strategy can be forced into this worst case, so smarter pivot selection alone cannot guarantee safety.

Musser’s Introspective Solution

David Musser (1997) introduced a meta‑strategy: monitor the recursion depth at runtime. When the depth exceeds twice the theoretical optimum (2 × ⌊log₂(n)⌋), the algorithm switches to heap sort, preserving the O(n log n) worst‑case bound. This self‑monitoring is the "intro" in introsort.

"16" – The Magic Threshold

The constant _S_threshold = 16 marks the point where recursion stops. Two cost analyses justify this value:

Recursion overhead: each recursive call saves registers, builds a stack frame (≈32‑64 bytes), and performs partition work. On modern x86 CPUs, a call‑return costs roughly 5‑10 simple comparisons, so for very small partitions the management cost outweighs the sorting work.

Insertion‑sort advantage on small data: Insertion sort’s worst‑case comparisons are n(n‑1)/2 (120 when n = 16), but after the quicksort phase the data is already nearly ordered, so actual work is far lower. Moreover, insertion sort on tiny arrays enjoys cache‑friendly sequential access, zero recursion overhead, and highly predictable branches.

Experimental studies by Bentley & Sedgewick (1993) showed the optimal range to be 8‑25 elements; libstdc++ therefore adopts 16 as the default, while MSVC uses 32.

2 × log₂(n) – The Depth Buffer

The depth limit depth_limit = 2 × ⌊log₂(n)⌋ tolerates moderate partition imbalance. If partitions are consistently 3:1 (75/25), the recursion depth becomes ≈2.4 × log₂(n). Setting the limit to 2 × log₂(n) allows such realistic imbalance while still catching pathological cases that would otherwise lead to O(n²) behaviour.

The Sentinel Trick in __final_insertion_sort

__final_insertion_sort

first sorts the first 16 elements with a boundary‑checked insertion sort, guaranteeing that the global minimum resides in this prefix. This element then acts as a sentinel for the subsequent __unguarded_insertion_sort, which omits the lower‑bound check entirely. By removing the if condition inside the inner loop, the algorithm eliminates millions of branch predictions; for n = 10⁶ this yields a 5‑10 % overall speed gain.

template<typename _RandomAccessIterator, typename _Compare>
void __final_insertion_sort(_RandomAccessIterator __first,
                             _RandomAccessIterator __last, _Compare __comp)
{
    if (__last - __first > int(_S_threshold))
    {
        // first 16 elements: insertion sort with bounds check
        std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
        // remaining elements: unguarded insertion sort
        std::__unguarded_insertion_sort(__first + int(_S_threshold), __last, __comp);
    }
    else
        std::__insertion_sort(__first, __last, __comp);
}

Practical Takeaway

For virtually all workloads, std::sort is the optimal choice. When it falls short, the remedy is rarely a custom comparison sort; instead, consider algorithms that target the specific need, such as std::partial_sort for the top‑k elements, std::nth_element for selection, or non‑comparison sorts like counting or radix sort.