Sorting Algorithms in C++

std::sort(begin, end) uses Introsort (Quick Sort + Heap Sort + Insertion Sort) for guaranteed O(n log n) — fast but not stable. std::stable_sort preserves equal-element order (Merge Sort based). std::sort_heap and std::partial_sort cover heap-based and top-k needs. Pass a comparator: std::sort(v.begin(), v.end(), std::greater<>()).

Introsort gets Quick Sort's cache-friendly speed, switches to Heap Sort to avoid the O(n²) worst case, and finishes with Insertion Sort on small partitions. Combined with C++'s zero-overhead abstractions and inlined comparators, it is the gold standard for in-memory sorting. See what std::sort uses.

void quickSort(std::vector<int>& a, int lo, int hi) {
    if (lo < hi) {
        int p = partition(a, lo, hi);
        quickSort(a, lo, p - 1);
        quickSort(a, p + 1, hi);
    }
}

std::sort is not one algorithm — it is introsort, a hybrid that switches strategy based on how the sort is going. This is why it manages to be both extremely fast in practice and immune to Quick Sort's quadratic worst case.

A typical implementation (libstdc++ is representative) works in three phases:

• Quick Sort is the main engine, using median-of-three pivot selection. This handles the bulk of the work with excellent cache locality.
• A recursion depth limit of roughly 2·log₂(n) is tracked. If partitioning keeps producing lopsided splits and the sort exceeds that depth, it abandons Quick Sort for the remaining range and finishes with Heap Sort, which guarantees O(n log n) and cannot degrade further.
• Insertion Sort finishes the job. Once partitions fall below a small threshold (16 in libstdc++), they are left unsorted and a single final Insertion Sort pass tidies the nearly-sorted whole array — which is exactly the input Insertion Sort is fastest on.

That depth-limit fallback is the important design idea. It means C++ can offer Quick Sort's real-world speed while the standard still guarantees O(n log n) worst-case complexity, which it has required since C++11.

The standard library gives you both, and the choice is a genuine trade-off rather than one being better.

One subtlety worth knowing: std::stable_sort tries to allocate a temporary buffer, and if that allocation fails it still works — it falls back to an in-place merge and degrades to O(n log²n) rather than failing outright. So it never runs out of memory on you; it just gets slower.

Use std::sort by default. Reach for std::stable_sort when equal elements have a meaningful existing order you need to preserve, which in practice means sorting structs or classes by one field while an earlier ordering still matters. If you only need the top few elements, std::partial_sort or std::nth_element will beat both.