Ask an interview candidate to sort and you’ll hear about quicksort. Ask what happens when they call list.sort() or std::sort and the honest answer is: something much more interesting. No mainstream standard library ships a textbook algorithm, because textbook algorithms optimize for random data and adversarial-free inputs — and real workloads are neither.

The Problem with the Textbook

Quicksort averages O(n log n) with great constants, but a bad pivot sequence makes it O(n²) — and “bad” isn’t rare in practice: already-sorted, reverse-sorted, and many-duplicates inputs break naive pivot choices, and an adversary can construct a killer input for any deterministic pivot rule (a real DoS vector — hash-flooding’s older cousin). Mergesort guarantees O(n log n) but pays allocation and copying. Heapsort guarantees it in place but with terrible cache behavior. So libraries compose them.

Introsort: C++‘s Defense in Depth

std::sort is introsort (introspective sort), and it’s three algorithms with an escape hatch:

text
  quicksort         — the fast path
  ├─ small partition (≲16 elements)? → insertion sort
  └─ recursion depth > 2·log₂(n)?    → heapsort for this partition

Insertion sort at the leaves wins because at 16 elements, O(n²) with sequential memory access and no recursion beats everything (the constant-factor story again). The depth limit is the clever part: if quicksort is degrading toward O(n²), the recursion gets deep, and introsort detects that and hands the offending partition to heapsort. Worst case: guaranteed O(n log n). The adversary loses by construction.

std::sort is not stable — equal elements may be reordered. std::stable_sort (mergesort-based) exists separately and costs more. Which brings us to Python.

Timsort: Betting on Structure

Python’s sort() — adopted later by Java for objects, and by Rust as the basis of its stable sort — is Timsort, built on a different observation: real data has runs. Log files are mostly chronological. Spreadsheets get re-sorted after small edits. Merged datasets are sorted chunks. Timsort finds structure and exploits it:

  1. Scan for existing runs (ascending, or descending → reversed in place).
  2. Extend short runs to a minimum length (~32) with insertion sort.
  3. Merge runs off a stack, maintaining size invariants that keep merging balanced.
  4. During merges, galloping mode: when one run keeps winning, switch from element-by-element comparison to exponential search and copy whole blocks.

The payoff is asymmetric: already-sorted input is O(n) — one scan, zero merges. Reverse-sorted is also O(n). Random data lands at ordinary O(n log n). And Timsort is stable, which is a feature with teeth: sort by name, then by department, and each department’s names stay alphabetical. Stability is what makes multi-key sorting composable.

(Aside for the formally inclined: the original merge-stack invariants had a bug that sat unnoticed for over a decade until a formal-verification effort found inputs that could overflow the run stack — fixed in CPython in 2015. Even battle-tested algorithms hide corners.)

Choosing, and Measuring

The practical decision table is short. Need stability (multi-key sorts, UI lists)? Timsort-family — in C++ that means std::stable_sort. Sorting primitives where stability is meaningless? Introsort-family, and note that Rust’s sort_unstable and recent C++ implementations use pattern-defeating quicksort (pdqsort), which adds Timsort-ish run detection to introsort — the two lineages are converging. Sorting by an expensive key? Precompute keys (decorate-sort-undecorate; Python’s key= does this for you) rather than recomputing per comparison — comparisons happen O(n log n) times.

And if sorting shows up in a profile, remember the exits: maybe you need a heap (top-k), a bucket/radix pass (integers with bounded range beat comparison sorting’s n log n floor entirely), or to maintain sorted order incrementally instead of re-sorting.

Takeaways

  • Standard libraries ship hybrids: introsort (quicksort + heapsort escape + insertion-sort leaves) and Timsort (run detection + balanced merges + galloping).
  • The designs encode two truths: worst cases must be structurally impossible, and real data has exploitable order.
  • Stability composes multi-key sorts; know whether your sort has it.
  • Small-n always goes to insertion sort — cache behavior beats asymptotics there.
  • Expensive comparators dominate: precompute keys, or escape comparison sorting altogether with radix/bucket/heap approaches.