# What Your Language's sort() Actually Runs

> Nobody ships textbook quicksort. Python runs Timsort, C++ runs introsort, and both are layered hybrids built around one insight: real-world data isn't random, and worst cases must be impossible.

URL: https://harshith.in/blog/how-sorting-actually-works/
Author: Harshith Sunku (Staff Engineer) — https://harshith.in/about/
Tags: algorithms, fundamentals, performance

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.