Sorting in the Real World
Textbook sorting ends at "merge sort is and stable, quicksort is on average and in place". Production sorting starts there. The sort() you call in Python, Java, C++, Rust, Go or JavaScript is a hybrid: a carefully tuned combination of insertion sort, merge sort, quicksort and heapsort that detects structure already present in the data, refuses to go quadratic on adversarial input, and keeps the constant factors low enough that a million integers sort in tens of milliseconds. When the data does not fit in memory at all, a different algorithm takes over — external merge sort — whose cost is measured in disk passes, not comparisons. This lesson is about both: what the libraries actually run, why, what they guarantee, and how sorting at the scale of databases and MapReduce works.
Lesson position: Module 2 · Searching & Sorting · previous: Non-Comparison Sorts · next: Binary Search Mastery · course map.
Why this exists
Every classic sort has a weakness that a library cannot afford. Plain quicksort is quadratic on sorted input with a naive pivot and on crafted input with any deterministic pivot — and "crafted input" is a real threat when the sort runs on data an attacker controls (McIlroy's 1999 paper "A Killer Adversary for Quicksort" builds such inputs on the fly against any quicksort). Merge sort needs extra memory and ignores the fact that real data is often already partly sorted: log files arrive in time order, a table is re-sorted after a few rows change, two sorted lists are concatenated. Heapsort has a guaranteed worst case and space but jumps across memory and runs two to three times slower than quicksort on modern CPUs. Insertion sort is the fastest algorithm there is for 10 elements and the slowest for 10,000.
So library authors combine them. Tim Peters wrote Timsort for Python 2.3 in 2002: a merge sort that finds the sorted stretches ("runs") already in the input, so sorted data costs . David Musser published introsort in 1997: quicksort that switches to heapsort when its recursion gets too deep, capping the worst case at . Orson Peters' pdqsort refines introsort to detect and exploit patterns. Knowing which one you are calling answers practical questions: is my sort stable, is it fast on nearly-sorted data, what happens if my comparator is wrong, how much memory does it take?
The second half of the story is size. A sort of 100 GB on a machine with 1 GB of RAM cannot hold the data, and random disk access is roughly five orders of magnitude slower than RAM. External merge sort — sort memory-sized chunks, write them out, merge them in a few sequential passes — was developed for tape drives in the 1950s and is still exactly what PostgreSQL does when an ORDER BY exceeds work_mem, what GNU sort does with a 50 GB file, and what Hadoop does between the map and reduce phases. Its cost model is not comparisons but passes over the data, and good engineering gets that down to two.
Pattern triggers
| If you see… | Think of… |
|---|---|
| "nearly sorted", "mostly in order", "appended a few records", "concatenation of sorted lists" | An adaptive sort (Timsort/Powersort, driftsort): on sorted input, for runs |
| "sort by A, then by B", "keep the original order of ties", sorting records by one field after another | Stability — Python sort, Java object sort, JS Array.prototype.sort (ES2019+), std::stable_sort, Rust sort |
| Sorting primitives in C++/Rust/Go/Java and you do not need stability | The unstable sort (introsort, pdqsort, ipnsort, dual-pivot quicksort): faster, no extra memory |
| "data does not fit in memory", "sort a 100 GB file", "1 GB of RAM" | External merge sort: run generation + -way merge with a heap |
| "merge sorted files / streams / lists" | A min-heap of heads — the merge phase of external sort (Heaps & Priority Queues) |
EXPLAIN ANALYZE shows Sort Method: external merge Disk: ... | The sort spilled past work_mem; see Query Planning & Optimization |
"only the top 10", ORDER BY ... LIMIT k | Do not sort everything: a bounded heap ("top-N heapsort") or quickselect |
IllegalArgumentException: Comparison method violates its general contract! | A comparator that is not a consistent total order — see Comparator pitfalls |
Intuition & first principles
Start from the question every hybrid answers: what does the input already tell us? A comparison sort must make comparisons in the worst case because there are possible orders to distinguish (the lower bound from the overview). But that bound is about the worst input. If the input is the concatenation of two sorted halves, only orders are possible and about comparisons suffice — one merge. If it consists of sorted runs of lengths , the information-theoretic cost is about where
is the entropy of the run lengths. is 0 for one run (already sorted) and when every run has length 1. An adaptive merge sort that achieves comparisons is optimal for every input, not just the worst one. That is the goal Timsort approximates and Powersort provably reaches.
The second question: how do we keep quicksort's speed without its worst case? Quicksort is fast because partitioning is a sequential scan with a tight inner loop and it sorts in place, so it is cache-friendly. Its weakness is only that a bad pivot sequence makes the recursion depth linear. Introsort's insight is to measure the damage: allow recursion depth up to about ; a good run of quicksort never reaches it, and if one does, heapsort finishes that subarray in guaranteed . You pay nothing on good inputs and cap the cost of bad ones.
The third question: what is the dominant cost? For an in-memory sort of 64-bit integers it is branch mispredictions and cache misses, not comparisons — which is why modern sorts use branchless partitioning and insertion sort for small slices. For a sort of 100 GB it is disk transfers, and a comparison is effectively free. The cost model changes the algorithm.
Here is how the major libraries map onto these ideas:
flowchart TD
Q["Need to sort"] --> F{"Fits in RAM?"}
F -->|"no"| EXT["External merge sort<br/>run generation + k-way merge"]
F -->|"yes"| S{"Stability required?"}
S -->|"yes"| ST["Adaptive merge sort<br/>Timsort / Powersort / driftsort"]
S -->|"no"| U["Introspective quicksort<br/>introsort / pdqsort / ipnsort / dual-pivot"]
ST --> PY["Python list.sort, Java objects,<br/>V8 Array.sort, Rust sort"]
U --> CPP["C++ std::sort, Rust sort_unstable,<br/>Go sort, Java primitives"]
EXT --> DB["Postgres tuplesort, GNU sort,<br/>Hadoop shuffle, Spark"]
Mechanics
Timsort: runs, minrun, merge stack, galloping
Step 1 — find runs. Scan left to right. A run is a maximal stretch that is non-descending () or strictly descending (). Descending runs are reversed in place. Strictness matters: reversing a run that contained equal elements would swap them and break stability, so equal neighbours always count as ascending.
Step 2 — enforce a minimum run length. Random data has runs of length about 2, and merging thousands of length-2 runs is wasteful. If a natural run is shorter than minrun, it is extended to minrun elements (or to the end of the array) with binary insertion sort — insertion sort that finds each insertion point by binary search, so it does comparisons per element (comparisons may be expensive Python objects) though still moves. Python picks minrun in so that is a power of two or slightly less, which keeps the final merges balanced: take the top six bits of and add 1 if any remaining bit is set. For the whole array is one insertion sort. Java's port uses .
| minrun | / minrun | |
|---|---|---|
| 63 | 63 | 1 (just insertion sort) |
| 64 | 32 | 2 |
| 65 | 33 | 1.97 |
| 128 | 32 | 4 |
| 1,000 | 63 | 15.9 |
| 2,112 | 33 | 64 |
| 1,000,000 | 62 | 16,129 |
(Computed with the CPython rule; the throwaway script is the minrun function in the Implementation variants.)
Step 3 — push each run on a stack and keep the stack balanced. Each run is pushed as (start, length). Merging only adjacent runs preserves stability. Timsort maintains, for the top three run lengths ( on top):
Whenever pushing a run violates either inequality, it merges with the smaller of and and re-checks. These invariants make the run lengths, read from the top down, grow at least as fast as Fibonacci numbers, so the stack has entries — Python preallocates 85 slots, enough for elements — and merges stay roughly balanced.
Step 4 — merge with galloping. Merging and first trims work: binary-search (gallop) for where 's first element belongs in — everything in before that point is already in place — and where 's last element belongs in . Only the overlap is merged, using a temporary buffer the size of the smaller run (merging left-to-right or right-to-left accordingly). During the merge, if one run "wins" MIN_GALLOP = 7 comparisons in a row, Timsort switches to galloping mode: it probes positions 1, 3, 7, 15, … in the winning run to find how many elements to copy in one block, then binary-searches within the last gap. This is exponential search, and it turns the merge of two runs that barely interleave from comparisons into . The threshold adapts: it decreases while galloping pays off and increases when it does not, so random data — where galloping wastes comparisons — quickly stops trying.
flowchart LR
A["Scan next run<br/>reverse if strictly descending"] --> B{"run length < minrun?"}
B -->|"yes"| C["Extend with<br/>binary insertion sort"]
B -->|"no"| D["Push run on stack"]
C --> D
D --> E{"Stack invariants hold?<br/>A > B+C and B > C"}
E -->|"no"| F["Merge B with smaller neighbour<br/>gallop to trim, then merge"]
F --> E
E -->|"yes"| G{"More input?"}
G -->|"yes"| A
G -->|"no"| H["Merge everything left<br/>top down"]
The 2015 invariant bug
In 2015 Stijn de Gouw, Jurriaan Rot, Frank de Boer, Richard Bubel and Reiner Hähnle tried to formally verify OpenJDK's java.util.TimSort with the KeY theorem prover and found that the implementation did not maintain the invariant it relied on. The merge routine (merge_collapse in CPython, mergeCollapse in Java) only checked the top three runs after each merge. A merge deep in the stack can create a new violation one level further down, which the check never looks at. Their paper, "OpenJDK's java.utils.Collection.sort() Is Broken: The Good, the Bad and the Worst Case" (CAV 2015), constructed inputs whose run lengths made the stack grow beyond its preallocated size, crashing Java's sort with an ArrayIndexOutOfBoundsException.
Here is the smallest illustration, computed with the original rule. The stack holds run lengths [120, 80, 25, 20] (bottom to top; invariants hold) and a run of length 30 arrives:
| Step | Stack (bottom → top) | Check on top three | Action |
|---|---|---|---|
| 0 | 120, 80, 25, 20, 30 | merge 25 and 20 (since , merge and ) | |
| 1 | 120, 80, 45, 30 | and | stop — looks fine |
| — | 120, 80, 45, 30 | but | invariant violated one level below the top three |
The fix in CPython (applied in the 2.7 and 3.4 maintenance lines in 2015) was to also check the run below : merge if or the run beneath is . With that rule the same stack collapses fully into a single run of 275. OpenJDK chose to enlarge the preallocated run stack so the reachable worst case fits (JDK-8072909) rather than change the merge rule. The episode is the most-cited example of formal verification finding a real bug in a library everyone trusted; the flawed rule had shipped in Python since 2002 and in Java since JDK 7.
Powersort: Python's merge policy since 3.11
Timsort's merge rule is a heuristic, and Buss and Knop (2019) showed families of run lengths on which it does markedly more merge work than necessary. J. Ian Munro and Sebastian Wild's Powersort ("Nearly-Optimal Mergesorts", ESA 2018) replaces only the policy — which adjacent runs to merge when — and keeps everything else (run detection, minrun, galloping merges). Each boundary between two adjacent runs gets a power: imagine the array as the interval , place each run at its midpoint, and the power of a boundary is the depth at which a perfectly balanced binary split of would first separate the midpoints of the two neighbouring runs. Runs are pushed as before, and before pushing a new run whose boundary has power , all stack entries with power greater than are merged. The result has merge cost at most , within an additive of optimal for every input. CPython adopted it in 3.11 (bpo-34561, committed by Tim Peters in September 2021); Objects/listsort.txt in the CPython repository documents both the original design and the change.
pdqsort and introsort
Introsort (Musser 1997) is quicksort with three additions: (1) median-of-three pivot selection; (2) a depth counter initialised to about — when it hits zero the current subarray is heapsorted; (3) subarrays of 16 or fewer elements are left unsorted and a single insertion sort pass over the whole array finishes them at the end. libstdc++'s std::sort is exactly this. libc++ (LLVM's library) was, embarrassingly, plain quicksort with an worst case until an introsort fallback landed for LLVM 14 in late 2021, closing a bug filed in 2014 (LLVM bug 20837) that pointed out the C++11 standard requires comparisons.
pdqsort ("pattern-defeating quicksort", Orson Peters; code 2015, paper arXiv:2106.05123 in 2021) keeps introsort's guarantee and adds:
- Bad-partition detection. A partition is "bad" if the smaller side has fewer than elements. After a bad partition, pdqsort swaps a few elements at fixed positions to break up whatever pattern caused it; after bad partitions it falls back to heapsort.
- Sorted-input detection. If a partition step performed no swaps, the subarray may already be sorted; pdqsort runs a partial insertion sort that gives up after 8 moves. Sorted and reverse-sorted inputs become .
- Many-equal-keys handling. If the chosen pivot equals the element just before the subarray (the previous pivot), every element equal to it is moved left in one pass and never touched again. An input with distinct values takes time instead of — linear when is small.
- Branchless block partitioning (from Edelkamp and Weiß's BlockQuicksort) for types whose comparison is cheap: comparison results are stored as offsets in a small buffer and swaps are done in bulk, removing the unpredictable branch from the inner loop.
pdqsort became Rust's slice::sort_unstable (Rust 1.20, 2017), Go's sort.Sort and slices.Sort (Go 1.19, 2022), and influenced Boost's pdqsort and later libc++ work.
Rust's 2024 switch: driftsort and ipnsort
Rust 1.81 (September 2024) replaced both standard sorts. slice::sort (stable) became driftsort by Orson Peters and Lukas Bergdoll: a run-adaptive merge sort with a Powersort-style policy that, for random regions, creates runs lazily with a stable quicksort instead of insertion sort, so it is adaptive like Timsort but competitive with unstable sorts on random data. slice::sort_unstable became ipnsort (Bergdoll), a pdqsort descendant that also detects a fully sorted or reversed input up front and uses specialised small-sorts for short slices. The release notes warn that the new implementations may panic if the Ord implementation is not a total order — they check for contract violations that the old code silently tolerated. They never cause memory unsafety; a wrong Ord gives an unspecified order or a panic.
Java's split: dual-pivot quicksort and Timsort
java.util.Arrays.sort has two families of overloads with different algorithms:
- Primitives (
int[],long[],double[], …): dual-pivot quicksort, by Vladimir Yaroslavskiy with Jon Bentley and Joshua Bloch, introduced in JDK 7 (2009). Two pivots split the array into three parts (, between, ). Wild and Nebel (2012) showed it does about 5% fewer comparisons than classic quicksort but more swaps, which does not by itself explain its speed; Kushagra et al. (2014) argued the real advantage is fewer passes over memory, hence fewer cache misses. Either way it was measurably faster on the JVM. Stability is irrelevant for primitives — two equalints are indistinguishable — so an unstable sort is free to win on speed. A 2019 rewrite (shipped in JDK 14) added run merging for nearly-sorted inputs and a heapsort fallback, giving a guaranteed . - Objects (
Object[],List.sort,Collections.sort): Timsort, Bloch's port of Python's, since JDK 7. Objects can have identity and satellite data, so the API promises stability, and comparisons of objects viacompareToare expensive enough that Timsort's frugality with comparisons pays off.
Arrays.parallelSort (JDK 8) splits the array, sorts pieces in the fork/join pool and merges them; it is worth it from roughly hundreds of thousands of elements on a multi-core machine.
V8's switch to Timsort
Before 2018, V8 (the JavaScript engine in Chrome and Node.js) used insertion sort for short arrays and quicksort otherwise — unstable. The V8 blog post "Getting things sorted in V8" (Simon Zünd, September 2018, v8.dev/blog/array-sort) describes the move to Timsort, written in V8's Torque language, shipped in V8 7.0 / Chrome 70. Two motivations: the ECMAScript spec was about to require stability (ES2019 made Array.prototype.sort stable), and the old JavaScript-implemented sort had performance cliffs and was hard to keep correct against user callbacks that mutate the array mid-sort. Every major engine is now stable.
Stability guarantees per language
A sort is stable if elements that compare equal keep their original relative order. Stability is what makes multi-key sorting by repeated sorts work: sort by the secondary key, then stably by the primary key.
| Language / call | Algorithm (current) | Stable? | Worst case | Extra memory |
|---|---|---|---|---|
Python list.sort, sorted | Timsort with Powersort merge policy (3.11+) | Yes, guaranteed | up to references | |
Java Arrays.sort(int[]) etc. | Dual-pivot quicksort | n/a (primitives) | since JDK 14 | |
Java Arrays.sort(Object[]), List.sort | Timsort | Yes, guaranteed | up to | |
C++ std::sort | Introsort (libstdc++, libc++ ≥ 14), MSVC similar | No | required since C++11 | |
C++ std::stable_sort | Merge sort | Yes | with buffer, without | if available |
Rust slice::sort | driftsort (1.81+) | Yes | (small cap for small types) | |
Rust slice::sort_unstable | ipnsort (1.81+), pdqsort before | No | ||
Go sort.Sort, slices.Sort | pdqsort (1.19+) | No | ||
Go sort.Stable, slices.SortStableFunc | Insertion sort blocks + in-place SymMerge | Yes | moves | |
JavaScript Array.prototype.sort | Timsort in V8; merge sorts elsewhere | Yes since ES2019 | ||
C# Array.Sort, List.Sort | Introsort | No | ||
C# LINQ OrderBy | Stable sort | Yes | ||
C qsort | Unspecified by the standard (glibc historically merge sort with fallback) | Not guaranteed | Not guaranteed | varies |
External merge sort: data larger than RAM
Suppose items must be sorted, memory holds items, and the disk transfers data in blocks of items. Random disk accesses are ruinous, so the algorithm reads and writes everything sequentially in two phases.
Phase 1 — run generation. Read items, sort them in memory (any fast internal sort), write them out as a sorted file, a run. Repeat. This produces runs and costs one read and one write of the data.
Phase 2 — -way merge. Open runs at once with one input buffer each, plus an output buffer. Put the head of each run in a min-heap keyed by value (ties broken by run index for stability). Repeatedly pop the smallest, append it to the output buffer, and push the next item from the same run; when an input buffer empties, refill it with the next block of that run; when the output buffer fills, write it. Each pop/push costs , so merging items costs CPU and one sequential read and write. With items of memory and -item buffers, the fan-in is . If there are more runs than , merge in groups of and repeat.
flowchart LR
IN["Unsorted input<br/>N items on disk"] --> RG["Phase 1: read M,<br/>sort in RAM, write run"]
RG --> R1["run 1"]
RG --> R2["run 2"]
RG --> R3["run ..."]
RG --> R4["run N/M"]
R1 --> H["Phase 2: min-heap<br/>of k run heads"]
R2 --> H
R3 --> H
R4 --> H
H --> OUT["Sorted output<br/>written sequentially"]
The I/O cost formula. Measured in block transfers, with blocks of data:
The factor 2 is read plus write; the 1 is run generation; the logarithm counts merge passes. Aggarwal and Vitter (1988) proved is optimal for sorting in this model, so external merge sort is asymptotically the best possible. Worked numbers (computed with a script; data volume in GB transferred is passes):
| Data | Memory | Buffer | Runs | Fan-in | Passes | Data moved |
|---|---|---|---|---|---|---|
| 100 GB | 1 GB | 1 MB | 100 | 1,023 | 2 | 400 GB |
| 100 GB | 1 GB | 64 MB | 100 | 15 | 3 | 600 GB |
| 1 TB | 256 MB | 1 MB | 4,096 | 255 | 3 | 6 TB |
| 1 TB | 64 MB | 8 MB | 16,384 | 7 | 6 | 12 TB |
| 10 GB | 4 MB | 8 KB | 2,560 | 511 | 3 | 60 GB |
Two lessons. Almost every realistic configuration finishes in two or three passes, because the logarithm's base is in the hundreds. And buffer size is a trade-off: bigger buffers mean fewer seeks but lower fan-in — the 64 MB-buffer row needs an extra pass. At a sequential 500 MB/s, the first row's 400 GB is about 800 seconds of pure transfer.
Replacement selection: runs of length about . Instead of sorting fixed chunks, keep a min-heap of items. Pop the smallest and write it to the current run; read the next input item; if it is the item just written it can still join the current run, so push it normally; otherwise tag it for the next run (it sorts after every current-run item). When the heap holds only next-run items, start a new run. On random input the average run length is — Knuth's "snowplow" argument in TAOCP Vol. 3, §5.4.1: picture a plough circling a track while snow falls uniformly; in steady state the snow in front of the plough is twice what it removes per lap. On already-sorted input the whole file becomes one run; on reverse-sorted input runs have length exactly . A simulation with random floats:
| Heap size | Items | Runs produced | Average run length / |
|---|---|---|---|
| 100 | 100,000 | 500 | 2.00 |
| 1,000 | 1,000,000 | 501 | 2.00 |
| 10,000 | 2,000,000 | 101 | 1.98 |
| 100 (sorted input) | 10,000 | 1 | 100 |
| 100 (reverse input) | 10,000 | 100 | 1 |
Halving the number of runs can save a whole merge pass. Its downside is that heap operations are slower per item than an in-memory quicksort on modern CPUs, which is why PostgreSQL switched run generation to quicksort in 9.6 and removed replacement selection entirely in 11.
Trace: external sort of 12 items with memory for 3
Input [9, 4, 7, 1, 8, 2, 6, 3, 5, 0, 11, 10], memory .
Phase 1 (chunk and sort): chunks [9,4,7], [1,8,2], [6,3,5], [0,11,10] become runs R0 = [4,7,9], R1 = [1,2,8], R2 = [3,5,6], R3 = [0,10,11].
Phase 2 (4-way merge with a heap), heap entries shown as (value, run), initial heap (0,R3) (1,R1) (3,R2) (4,R0):
| Step | Pop | Push next from same run | Heap after | Output so far |
|---|---|---|---|---|
| 1 | (0, R3) | (10, R3) | (1,R1) (3,R2) (4,R0) (10,R3) | 0 |
| 2 | (1, R1) | (2, R1) | (2,R1) (3,R2) (4,R0) (10,R3) | 0 1 |
| 3 | (2, R1) | (8, R1) | (3,R2) (4,R0) (8,R1) (10,R3) | 0 1 2 |
| 4 | (3, R2) | (5, R2) | (4,R0) (5,R2) (8,R1) (10,R3) | 0 … 3 |
| 5 | (4, R0) | (7, R0) | (5,R2) (7,R0) (8,R1) (10,R3) | 0 … 4 |
| 6 | (5, R2) | (6, R2) | (6,R2) (7,R0) (8,R1) (10,R3) | 0 … 5 |
| 7 | (6, R2) | — (R2 exhausted) | (7,R0) (8,R1) (10,R3) | 0 … 6 |
| 8 | (7, R0) | (9, R0) | (8,R1) (9,R0) (10,R3) | 0 … 7 |
| 9 | (8, R1) | — (R1 exhausted) | (9,R0) (10,R3) | 0 … 8 |
| 10 | (9, R0) | — (R0 exhausted) | (10,R3) | 0 … 9 |
| 11 | (10, R3) | (11, R3) | (11,R3) | 0 … 10 |
| 12 | (11, R3) | — | empty | 0 … 11 |
Replacement selection on the same input with a heap of 3 (tags in parentheses are the run number an item will join):
| Out | Read next | Goes to | Heap after (run, value) |
|---|---|---|---|
| 4 (run 0) | 1 | run 1 () | (0,7) (0,9) (1,1) |
| 7 (run 0) | 8 | run 0 () | (0,8) (0,9) (1,1) |
| 8 (run 0) | 2 | run 1 | (0,9) (1,1) (1,2) |
| 9 (run 0) | 6 | run 1 | (1,1) (1,2) (1,6) |
| 1 (run 1) | 3 | run 1 | (1,2) (1,3) (1,6) |
| 2 (run 1) | 5 | run 1 | (1,3) (1,5) (1,6) |
| 3 (run 1) | 0 | run 2 | (1,5) (1,6) (2,0) |
| 5 (run 1) | 11 | run 1 | (1,6) (1,11) (2,0) |
| 6 (run 1) | 10 | run 1 | (1,10) (1,11) (2,0) |
| 10 (run 1) | — | — | (1,11) (2,0) |
| 11 (run 1) | — | — | (2,0) |
| 0 (run 2) | — | — | empty |
Runs: [4,7,8,9], [1,2,3,5,6,10,11], [0] — three runs instead of four, the middle one more than twice the memory size.
The ladder: brute force → better → optimal
The question here is "sort items that do not fit in memory ". Each rung is a real strategy someone has shipped.
Rung 1 — pretend it fits (virtual memory). Load everything, call the in-memory sort, let the OS page. Quicksort's partition scans are sequential and survive paging tolerably; merge sort's buffer doubles the footprint; heapsort's jumps across the array cause a page fault on almost every access. With data 100× RAM, each page fault is a random disk read: millions of them, hours to days. Complexity in I/Os: up to random transfers. It improves on nothing; it is the baseline to beat.
Rung 2 — chunk, sort, 2-way merge passes. Sort -sized runs, then merge pairs of runs repeatedly. Every access is sequential. Passes: . For 100 GB with 1 GB memory that is passes, 1.6 TB moved. Better because each transfer is sequential and useful, but the base-2 logarithm wastes memory: a 2-way merge needs only three buffers.
Rung 3 — -way merge with a heap. Use all of memory as input buffers and merge them all at once with a min-heap. Passes drop to — 2 for the 100 GB case, 400 GB moved. This is the asymptotically optimal I/O bound. CPU per item rises from to comparisons in the merge, irrelevant next to disk time.
Rung 4 — fewer, longer runs and overlapped I/O. Replacement selection (or exploiting natural runs, as Timsort does) halves the number of runs on random input and collapses sorted input to one run; double-buffering lets the next block load while the current one is merged, hiding latency; compressing runs trades CPU for I/O. Same asymptotic cost, smaller constants.
| Rung | Passes for 100 GB / 1 GB RAM / 1 MB blocks | Access pattern | Extra idea |
|---|---|---|---|
| 1. Sort in virtual memory | not meaningful (random faults) | random | none |
| 2. Runs + 2-way merges | 8 | sequential | run generation |
| 3. Runs + -way heap merge | 2 | sequential | use all memory as fan-in |
| 4. + replacement selection, overlap | 2 (fewer runs, less wall time) | sequential, overlapped | longer runs, prefetch |
Correctness
The k-way merge outputs a sorted permutation
Invariant. Before each pop, (1) the output is sorted, (2) every element in the output is every element not yet output, and (3) the heap contains exactly the first not-yet-output element of each non-exhausted run.
Initialisation. Output is empty; the heap holds each run's first element. All three hold trivially.
Maintenance. Let from run be the heap minimum. Every unoutput element lies in some run at or after that run's head; each run is sorted, so every unoutput element is some head, and every head is . Hence is the minimum of all unoutput elements. Appending it keeps the output sorted (by (2), everything already output) and keeps (2) true. Pushing run 's next element restores (3).
Termination. Each step outputs one element; after steps the heap is empty, all elements are output, and by (1) they are sorted. No element is duplicated or lost because each is pushed exactly once (when its predecessor in its run is popped, or initially) and popped exactly once.
Stability. Breaking heap ties by run index, and numbering runs in input order, makes equal elements leave in input order: within a run they stay in order (the chunk sort was stable), and across runs the lower index — earlier in the input — wins.
Multi-pass merging terminates in the stated number of passes
Each merge pass replaces groups of runs by one, so runs become . After passes there are runs, which equals 1 exactly when , i.e. . Adding the run-generation pass gives the formula above.
Replacement selection produces sorted runs
Claim: items written while the current run number is form a non-decreasing sequence. Items tagged are, by construction, either initial items (tag 0) or items read when the last output satisfied . The heap orders by (tag, value), so while any tag- item exists it is popped before any tag- item, and among tag- items in value order. Suppose output (tag ) is followed by output (tag ). Either was in the heap when was popped — then because was the minimum — or was read later, after some output (outputs within the run are non-decreasing by induction), and it was tagged only because . Either way .
Why Timsort's invariant bounds the stack
If every three consecutive run lengths satisfy and , then reading from the top, lengths and — Fibonacci-like growth. The -th entry from the top is at least (a Fibonacci number), and the sum of all entries is at most , so the depth is at most . The 2015 bug is precisely that the code did not establish the hypothesis for every triple, only the top one, so this bound did not apply and the stack overflowed.
Introsort's worst case
Each level of quicksort recursion does partition work across all subarrays at that level. Recursion is cut at depth , so quicksort contributes at most . Any subarray handed to heapsort of size costs , and those subarrays are disjoint, so together they cost . The final insertion sort touches elements only within blocks of 16 (every element is already in its final block after partitioning), so it is . Total: in the worst case.
Complexity
| Algorithm | Best | Average | Worst | Extra space | Notes |
|---|---|---|---|---|---|
| Timsort / Powersort | (sorted, reversed) | ; adaptively | Powersort's merge cost | ||
| Introsort | stack | libstdc++ std::sort | |||
| pdqsort / ipnsort | (sorted, few distinct) | for distinct keys | |||
| Dual-pivot quicksort (JDK 14+) | (detected runs) | primitives only | |||
| External merge sort | — | — | I/Os | memory, temp disk | CPU total |
Constants and the machine. For in-memory sorts of small keys, mispredicted branches dominate: a random comparison is a coin flip for the branch predictor. Branchless block partitioning (pdqsort, BlockQuicksort) removes that cost; insertion sort below 16–32 elements wins because its loop is tiny and its data sits in L1. Timsort shines when comparisons are expensive (Python objects, compareTo calls) because it does close to the information-theoretic minimum number of them. For external sorts CPU is noise next to I/O until the device is NVMe; then parsing and comparing records dominates, which is why PostgreSQL uses abbreviated keys (compare a fixed-size integer prefix of each string key, and the full key only on ties).
Implementation
The canonical implementation simulates an external merge sort on generated data: "disk" is a list of runs, memory is a chunk size, and the fan-in limits how many runs a merge pass may open. It counts runs, merge passes, and element transfers (one read plus one write per item per pass), so the I/O formula can be checked. The data generator is the Park–Miller "minimal standard" LCG, chosen because — the products fit exactly in JavaScript doubles, so all four languages generate identical data.
import heapq
def lcg_data(n: int, seed: int = 42) -> list[int]:
"""Deterministic pseudo-random ints in [0, 10^6) - identical in all four languages."""
x, out = seed, []
for _ in range(n):
x = (x * 48271) % 2147483647
out.append(x % 1_000_000)
return out
def generate_runs(data: list[int], memory: int) -> list[list[int]]:
"""Phase 1: read `memory` items at a time, sort them in RAM, 'write' a run."""
return [sorted(data[i:i + memory]) for i in range(0, len(data), memory)]
def k_way_merge(runs: list[list[int]]) -> list[int]:
"""Phase 2: min-heap of (value, run index, position); ties go to the lower run (stable)."""
heap = [(run[0], r, 0) for r, run in enumerate(runs) if run]
heapq.heapify(heap)
out: list[int] = []
while heap:
value, r, i = heapq.heappop(heap)
out.append(value)
if i + 1 < len(runs[r]):
heapq.heappush(heap, (runs[r][i + 1], r, i + 1))
return out
def external_sort(data: list[int], memory: int, fan_in: int) -> tuple[list[int], dict]:
runs = generate_runs(data, memory)
stats = {"runs": len(runs), "merge_passes": 0, "io": 2 * len(data)}
while len(runs) > 1:
runs = [k_way_merge(runs[i:i + fan_in]) for i in range(0, len(runs), fan_in)]
stats["merge_passes"] += 1
stats["io"] += 2 * len(data) # every item read once and written once per pass
return (runs[0] if runs else []), stats
if __name__ == "__main__":
small = [9, 4, 7, 1, 8, 2, 6, 3, 5, 0, 11, 10]
assert generate_runs(small, 3) == [[4, 7, 9], [1, 2, 8], [3, 5, 6], [0, 10, 11]]
out, st = external_sort(small, 3, 4)
assert out == list(range(12)) and st == {"runs": 4, "merge_passes": 1, "io": 48}
out, st = external_sort(small, 3, 2)
assert out == list(range(12)) and st["merge_passes"] == 2
data = lcg_data(10_000)
assert data[:3] == [27382, 992407, 494037]
out, st = external_sort(data, 1_000, 4) # 10 runs -> 3 -> 1
assert out == sorted(data)
assert st == {"runs": 10, "merge_passes": 2, "io": 60_000}
assert out[:3] == [209, 316, 331] and out[-1] == 999958
assert external_sort([], 3, 2)[0] == []
print("ok")
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
public class ExternalSort {
record Result(int[] sorted, int runs, int mergePasses, long io) {}
static int[] lcgData(int n, long seed) {
int[] out = new int[n];
long x = seed;
for (int i = 0; i < n; i++) {
x = (x * 48271L) % 2147483647L;
out[i] = (int) (x % 1_000_000L);
}
return out;
}
static List<int[]> generateRuns(int[] data, int memory) {
List<int[]> runs = new ArrayList<>();
for (int i = 0; i < data.length; i += memory) {
int[] chunk = Arrays.copyOfRange(data, i, Math.min(data.length, i + memory));
Arrays.sort(chunk);
runs.add(chunk);
}
return runs;
}
static int[] kWayMerge(List<int[]> runs) {
int total = 0;
for (int[] r : runs) total += r.length;
int[] out = new int[total];
// heap entry: {value, run index, position in run}; ties broken by run index
PriorityQueue<int[]> heap = new PriorityQueue<>(
(p, q) -> p[0] != q[0] ? Integer.compare(p[0], q[0]) : Integer.compare(p[1], q[1]));
for (int r = 0; r < runs.size(); r++)
if (runs.get(r).length > 0) heap.add(new int[]{runs.get(r)[0], r, 0});
int k = 0;
while (!heap.isEmpty()) {
int[] top = heap.poll();
out[k++] = top[0];
int[] run = runs.get(top[1]);
int next = top[2] + 1;
if (next < run.length) heap.add(new int[]{run[next], top[1], next});
}
return out;
}
static Result externalSort(int[] data, int memory, int fanIn) {
List<int[]> runs = generateRuns(data, memory);
int initialRuns = runs.size();
long io = 2L * data.length;
int passes = 0;
while (runs.size() > 1) {
List<int[]> next = new ArrayList<>();
for (int i = 0; i < runs.size(); i += fanIn)
next.add(kWayMerge(runs.subList(i, Math.min(runs.size(), i + fanIn))));
runs = next;
passes++;
io += 2L * data.length;
}
return new Result(runs.isEmpty() ? new int[0] : runs.get(0), initialRuns, passes, io);
}
static void check(boolean ok, String what) {
if (!ok) throw new AssertionError(what);
}
public static void main(String[] args) {
int[] small = {9, 4, 7, 1, 8, 2, 6, 3, 5, 0, 11, 10};
int[] expected = new int[12];
for (int i = 0; i < 12; i++) expected[i] = i;
List<int[]> runs = generateRuns(small, 3);
check(Arrays.equals(runs.get(0), new int[]{4, 7, 9}) && Arrays.equals(runs.get(3), new int[]{0, 10, 11}), "runs");
Result r = externalSort(small, 3, 4);
check(Arrays.equals(r.sorted(), expected) && r.runs() == 4 && r.mergePasses() == 1 && r.io() == 48, "small 4-way");
r = externalSort(small, 3, 2);
check(Arrays.equals(r.sorted(), expected) && r.mergePasses() == 2, "small 2-way");
int[] data = lcgData(10_000, 42);
check(data[0] == 27382 && data[1] == 992407 && data[2] == 494037, "lcg");
r = externalSort(data, 1_000, 4);
int[] ref = data.clone();
Arrays.sort(ref);
check(Arrays.equals(r.sorted(), ref), "sorted");
check(r.runs() == 10 && r.mergePasses() == 2 && r.io() == 60_000, "stats");
check(r.sorted()[0] == 209 && r.sorted()[9_999] == 999958, "ends");
check(externalSort(new int[0], 3, 2).sorted().length == 0, "empty");
System.out.println("ok");
}
}
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <functional>
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
using Run = std::vector<int>;
struct Result {
Run sorted;
int runs;
int merge_passes;
long long io;
};
std::vector<int> lcg_data(int n, std::int64_t seed = 42) {
std::vector<int> out;
out.reserve(n);
std::int64_t x = seed;
for (int i = 0; i < n; ++i) {
x = (x * 48271) % 2147483647;
out.push_back(static_cast<int>(x % 1000000));
}
return out;
}
std::vector<Run> generate_runs(const std::vector<int>& data, int memory) {
std::vector<Run> runs;
for (std::size_t i = 0; i < data.size(); i += memory) {
Run chunk(data.begin() + i, data.begin() + std::min(data.size(), i + memory));
std::sort(chunk.begin(), chunk.end());
runs.push_back(std::move(chunk));
}
return runs;
}
Run k_way_merge(const std::vector<Run>& runs, std::size_t first, std::size_t last) {
// (value, run index, position) - tuple order breaks ties by run index
using Entry = std::tuple<int, std::size_t, std::size_t>;
std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> heap;
std::size_t total = 0;
for (std::size_t r = first; r < last; ++r) {
total += runs[r].size();
if (!runs[r].empty()) heap.emplace(runs[r][0], r, 0);
}
Run out;
out.reserve(total);
while (!heap.empty()) {
auto [value, r, i] = heap.top();
heap.pop();
out.push_back(value);
if (i + 1 < runs[r].size()) heap.emplace(runs[r][i + 1], r, i + 1);
}
return out;
}
Result external_sort(const std::vector<int>& data, int memory, int fan_in) {
std::vector<Run> runs = generate_runs(data, memory);
Result res{{}, static_cast<int>(runs.size()), 0, 2LL * static_cast<long long>(data.size())};
while (runs.size() > 1) {
std::vector<Run> next;
for (std::size_t i = 0; i < runs.size(); i += fan_in)
next.push_back(k_way_merge(runs, i, std::min(runs.size(), i + fan_in)));
runs = std::move(next);
++res.merge_passes;
res.io += 2LL * static_cast<long long>(data.size());
}
if (!runs.empty()) res.sorted = std::move(runs[0]);
return res;
}
int main() {
std::vector<int> small{9, 4, 7, 1, 8, 2, 6, 3, 5, 0, 11, 10};
std::vector<int> expected(12);
for (int i = 0; i < 12; ++i) expected[i] = i;
auto runs = generate_runs(small, 3);
assert((runs[0] == Run{4, 7, 9}) && (runs[3] == Run{0, 10, 11}));
Result r = external_sort(small, 3, 4);
assert(r.sorted == expected && r.runs == 4 && r.merge_passes == 1 && r.io == 48);
r = external_sort(small, 3, 2);
assert(r.sorted == expected && r.merge_passes == 2);
auto data = lcg_data(10000);
assert(data[0] == 27382 && data[1] == 992407 && data[2] == 494037);
r = external_sort(data, 1000, 4);
auto ref = data;
std::sort(ref.begin(), ref.end());
assert(r.sorted == ref);
assert(r.runs == 10 && r.merge_passes == 2 && r.io == 60000);
assert(r.sorted.front() == 209 && r.sorted.back() == 999958);
assert(external_sort({}, 3, 2).sorted.empty());
std::cout << "ok\n";
}
type Entry = [value: number, run: number, pos: number];
function lcgData(n: number, seed = 42): number[] {
// 48271 * (2^31 - 1) < 2^53, so these products are exact in doubles
let x = seed;
const out: number[] = [];
for (let i = 0; i < n; i++) {
x = (x * 48271) % 2147483647;
out.push(x % 1_000_000);
}
return out;
}
function generateRuns(data: number[], memory: number): number[][] {
const runs: number[][] = [];
for (let i = 0; i < data.length; i += memory) {
runs.push(data.slice(i, i + memory).sort((a, b) => a - b));
}
return runs;
}
class MinHeap {
private a: Entry[] = [];
get size(): number { return this.a.length; }
private less(i: number, j: number): boolean {
const [x, y] = [this.a[i], this.a[j]];
return x[0] !== y[0] ? x[0] < y[0] : x[1] < y[1];
}
push(e: Entry): void {
this.a.push(e);
let i = this.a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (!this.less(i, p)) break;
[this.a[i], this.a[p]] = [this.a[p], this.a[i]];
i = p;
}
}
pop(): Entry {
const top = this.a[0];
const last = this.a.pop()!;
if (this.a.length > 0) {
this.a[0] = last;
let i = 0;
for (;;) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < this.a.length && this.less(l, m)) m = l;
if (r < this.a.length && this.less(r, m)) m = r;
if (m === i) break;
[this.a[i], this.a[m]] = [this.a[m], this.a[i]];
i = m;
}
}
return top;
}
}
function kWayMerge(runs: number[][]): number[] {
const heap = new MinHeap();
runs.forEach((run, r) => { if (run.length > 0) heap.push([run[0], r, 0]); });
const out: number[] = [];
while (heap.size > 0) {
const [value, r, i] = heap.pop();
out.push(value);
if (i + 1 < runs[r].length) heap.push([runs[r][i + 1], r, i + 1]);
}
return out;
}
function externalSort(data: number[], memory: number, fanIn: number) {
let runs = generateRuns(data, memory);
const stats = { runs: runs.length, mergePasses: 0, io: 2 * data.length };
while (runs.length > 1) {
const next: number[][] = [];
for (let i = 0; i < runs.length; i += fanIn) next.push(kWayMerge(runs.slice(i, i + fanIn)));
runs = next;
stats.mergePasses++;
stats.io += 2 * data.length;
}
return { sorted: runs.length > 0 ? runs[0] : [], ...stats };
}
function assert(cond: boolean, what: string): void {
if (!cond) throw new Error("assertion failed: " + what);
}
const same = (a: number[], b: number[]) => a.length === b.length && a.every((v, i) => v === b[i]);
const small = [9, 4, 7, 1, 8, 2, 6, 3, 5, 0, 11, 10];
const expected = Array.from({ length: 12 }, (_, i) => i);
const runs0 = generateRuns(small, 3);
assert(same(runs0[0], [4, 7, 9]) && same(runs0[3], [0, 10, 11]), "runs");
let r = externalSort(small, 3, 4);
assert(same(r.sorted, expected) && r.runs === 4 && r.mergePasses === 1 && r.io === 48, "small 4-way");
r = externalSort(small, 3, 2);
assert(same(r.sorted, expected) && r.mergePasses === 2, "small 2-way");
const data = lcgData(10_000);
assert(same(data.slice(0, 3), [27382, 992407, 494037]), "lcg");
r = externalSort(data, 1_000, 4);
assert(same(r.sorted, [...data].sort((a, b) => a - b)), "sorted");
assert(r.runs === 10 && r.mergePasses === 2 && r.io === 60_000, "stats");
assert(r.sorted[0] === 209 && r.sorted[9_999] === 999958, "ends");
assert(externalSort([], 3, 2).sorted.length === 0, "empty");
console.log("ok");
Variant: replacement selection and Timsort's minrun
Two small, runnable pieces from the Mechanics section: replacement selection (the heap trick for -long runs) and CPython's minrun computation.
import heapq
import random
def replacement_selection(data: list[int], memory: int) -> list[list[int]]:
it = iter(data)
heap = [(0, x) for _, x in zip(range(memory), it)] # (run tag, value)
heapq.heapify(heap)
runs: list[list[int]] = []
current, run = [], 0
while heap:
tag, x = heapq.heappop(heap)
if tag != run: # only next-run items remain: start a new run
runs.append(current)
current, run = [], tag
current.append(x)
y = next(it, None)
if y is not None:
heapq.heappush(heap, (run if y >= x else run + 1, y))
if current:
runs.append(current)
return runs
def minrun(n: int) -> int:
r = 0
while n >= 64:
r |= n & 1
n >>= 1
return n + r
small = [9, 4, 7, 1, 8, 2, 6, 3, 5, 0, 11, 10]
assert replacement_selection(small, 3) == [[4, 7, 8, 9], [1, 2, 3, 5, 6, 10, 11], [0]]
assert len(replacement_selection(list(range(10_000)), 100)) == 1 # sorted: one run
assert len(replacement_selection(list(range(10_000, 0, -1)), 100)) == 100 # reversed: runs of M
random.seed(1)
rand = [random.random() for _ in range(100_000)]
runs = replacement_selection(rand, 100)
assert all(r == sorted(r) for r in runs)
assert 1.9 < len(rand) / len(runs) / 100 < 2.1 # average run about 2M
assert [minrun(n) for n in (63, 64, 65, 128, 1000, 2112, 10**6)] == [63, 32, 33, 32, 63, 33, 62]
print("ok")
Real-world uses
PostgreSQL's sort operator. tuplesort.c sorts in memory with quicksort as long as the tuples fit in work_mem (default 4 MB, per sort operation, per query node — a query with three sorts can use three times that). Beyond it, the sort becomes external: it writes sorted runs to temporary files ("logical tapes") and merges them. EXPLAIN ANALYZE reports which happened: Sort Method: quicksort Memory: 3120kB versus Sort Method: external merge Disk: 51200kB. For ORDER BY … LIMIT k it reports top-N heapsort — a bounded heap of tuples instead of a full sort. Run generation has used quicksort since 9.6, and PostgreSQL 15 replaced the classic polyphase merge (a tape-era scheme for merging with few drives) with a simple balanced -way merge, which the commit and later benchmarks reported as noticeably faster for sorts needing multiple merge passes. Raising work_mem for one session (SET work_mem = '256MB') is the standard fix for a large sort that spills; the planner also uses sort cost to choose between merge join, hash join and index scans that deliver rows already ordered. See Query Planning & Optimization and How Databases Work.
Index builds and LSM compaction. CREATE INDEX on a B-tree sorts all keys (external sort if needed) and builds the tree bottom-up from the sorted stream — far faster than inserting keys one at a time. LSM-tree storage engines (RocksDB, Cassandra, LevelDB) are external merge sort as an architecture: memtables are flushed as sorted runs (SSTables), and compaction is a -way merge of sorted files. See Storage Engines and Indexing Deep Dive.
GNU sort. Coreutils sort is a merge sort that becomes external automatically: it sorts buffer-sized chunks (-S / --buffer-size, default chosen from available memory), writes temporary files to $TMPDIR or -T dir, and merges at most --batch-size files at once (default 16), merging in multiple passes if there are more. --parallel=N sorts chunks on several threads. Two practical facts: LC_ALL=C sort compares bytes instead of applying locale collation rules and is often several times faster; and when all keys compare equal GNU sort falls back to comparing whole lines unless you pass -s (stable), which changes output order for key-based sorts. sort -m merges already-sorted files without re-sorting — the merge phase alone.
MapReduce, Hadoop and Spark. Dean and Ghemawat's MapReduce paper (OSDI 2004) guarantees that each reducer sees its keys in sorted order. Map outputs are partitioned by hash(key) mod R, sorted within each partition, and spilled to local disk; each reducer fetches its partition from every mapper and merges the sorted pieces — the shuffle is a distributed external merge sort. In Hadoop the map side collects output in a circular memory buffer (mapreduce.task.io.sort.mb, 100 MB by default), spills sorted runs when it is about 80% full, and merges spills with fan-in mapreduce.task.io.sort.factor (default 10). Spark has used a sort-based shuffle by default since 1.2.
Operating systems and systems code. The Linux kernel's lib/sort.c is a heapsort — chosen for its extra space and bounded worst case, which matter more in the kernel than raw speed; see OS Algorithms. Memory allocators keep free lists sorted by address to coalesce neighbours (Memory Allocators).
Pitfalls & edge cases
Comparator pitfalls
A comparison sort is correct only if the comparator is a strict weak ordering: irreflexive ( is false), transitive ( and imply ), and with "incomparable" (neither nor ) also transitive — equivalence classes behave like equal values. Violations are not caught at compile time, and each language fails differently:
- Java (
Comparatorused by Timsort): if Timsort notices an inconsistency during a merge it throwsIllegalArgumentException: Comparison method violates its general contract!. Not every violation is noticed; you may also get silently wrong order. Common causes: a comparator that never returns 0 ((a, b) -> a < b ? -1 : 1), comparing by mutable fields that change during the sort, random comparators used to "shuffle", and comparators with mixed criteria that are not transitive. The JVM flag-Djava.util.Arrays.useLegacyMergeSort=truerestores the pre-JDK-7 merge sort that silently tolerates such comparators — a crutch, not a fix. - C++ (
std::sort): a comparator that is not a strict weak ordering is undefined behaviour. With libstdc++,std::sort(v.begin(), v.end(), [](int a, int b) { return a <= b; })can run its unguarded insertion sort off the end of the array and corrupt memory or crash. Always use<, never<=. - Rust (1.81+): may panic on a non-total
Ord; never memory-unsafe. - Python: never crashes on an inconsistent comparison; it silently returns some permutation. It raises
ValueError: list modified during sortif a key function mutates the list, andTypeErrorwhen comparing incomparable types ([1, "a"]). - JavaScript: the default comparator converts elements to strings:
[10, 9, 1].sort()gives[1, 10, 9]. Always pass(a, b) => a - bfor numbers.
The subtraction comparator. return a - b; in Java or C overflows for large magnitudes: comparing Integer.MIN_VALUE and 1 gives a positive difference, claiming the minimum is larger. Use Integer.compare(a, b) or (a > b) - (a < b).
NaN. IEEE 754 makes every comparison with NaN false, so NaN is "incomparable" with everything — but the equivalence it induces is not transitive (1 ~ NaN and NaN ~ 2, yet 1 < 2). A sort over floats containing NaN can return garbage in Python, panic in Rust (partial_cmp(...).unwrap() on NaN), or be undefined in C++. Use a total order: Java's Double.compare puts NaN last, Rust has f64::total_cmp, in Python filter NaNs or key on (math.isnan(x), x).
import math
nan = float("nan")
out = sorted([3, nan, 1, 2])
non_nan = [x for x in out if not math.isnan(x)]
assert non_nan != sorted(non_nan) # with NaN present the result is NOT sorted
assert out[0] == 3 # here Python returned [3, nan, 1, 2]
fixed = sorted([3, nan, 1, 2], key=lambda x: (math.isnan(x), x))
assert fixed[:3] == [1, 2, 3] and math.isnan(fixed[3])
print("ok")
And the Java contract violation, reproduced deterministically with a seeded "random" comparator on JDK 21 (a common mistake when people try to shuffle with sort):
import java.util.Arrays;
import java.util.Random;
public class ContractViolation {
public static void main(String[] args) {
Random rnd = new Random(7);
int thrown = 0;
for (int trial = 0; trial < 20; trial++) {
Integer[] xs = new Integer[1000];
for (int i = 0; i < xs.length; i++) xs[i] = rnd.nextInt(1000);
try {
Arrays.sort(xs, (p, q) -> rnd.nextInt(3) - 1); // NOT a valid ordering
} catch (IllegalArgumentException e) {
thrown++; // "Comparison method violates its general contract!"
}
}
if (thrown == 0) throw new AssertionError("expected at least one contract violation");
System.out.println("contract violations detected in " + thrown + " of 20 sorts");
}
}
Other edge cases
- Sorting by key with expensive keys.
sorted(xs, key=f)callsfonce per element (decorate–sort–undecorate); acmp-style comparator calls its logic times. In Java,Comparator.comparing(f)callsfon every comparison — precompute for expensive keys. - External sort temp space. A spill needs about as much free temporary disk as the data (more if runs are not compressed). PostgreSQL's
temp_file_limit, GNUsort -Tand Hadoop's local dirs exist because sorts fill disks. - Too many open files. A 4,096-way merge opens 4,096 files; the default
ulimit -nis often 1,024. That is one reason GNU sort caps fan-in at 16 by default. - Duplicates in quicksort. A two-way Lomuto partition on an array of all-equal keys is quadratic. Every library sort handles this (three-way partition or pdqsort's equal-pivot trick); a hand-written quicksort often does not.
Variations
- Introselect /
std::nth_element— the selection analogue of introsort: quickselect with a fallback to guarantee linear-ish worst case. See Quickselect & Order Statistics. - Partial sort / top- —
std::partial_sort(heap),heapq.nlargest, PostgreSQL's top-N heapsort: instead of . - Polyphase merge — merge with an uneven Fibonacci-distributed set of runs across few tapes so no tape sits idle; essential with 3–4 tape drives, obsolete with disks (PostgreSQL dropped it in 15).
- Distribution (bucket) external sort — partition by key range into buckets that fit in memory, sort each; one pass if the key distribution is known (TeraSort samples keys to pick range boundaries). See Non-Comparison Sorts.
- Parallel and distributed sorts — sample sort (pick splitters, scatter, sort locally),
Arrays.parallelSort, C++17 parallelstd::sort, GPU radix sort. - Vectorised sorts — Google's Highway VQSort and Intel's x86-simd-sort use AVX-512 / SIMD sorting networks inside quicksort; NumPy adopted SIMD sorting for some dtypes.
Practice ladder
Easy → hard. Descriptions are paraphrased; follow the links for exact statements.
1. Sort an Array (LeetCode 912) — sort integers in without the built-in sort. Teaches writing a production-grade hybrid: insertion sort below a cutoff, a real worst-case guarantee.
Hint
Merge sort with an insertion-sort cutoff of ~16 is the safest; a quicksort here meets adversarial tests (many duplicates, sorted input) — use three-way partitioning and a random pivot if you choose it.
2. Merge Sorted Array (LeetCode 88) — merge two sorted arrays in place when the first has room at the end. Teaches merging from the back, the same trick as Timsort's merge_hi.
Hint
Fill positions from the end with the larger of the two tails; nothing is overwritten before it is read.
3. Relative Sort Array (LeetCode 1122) — order one array by the order of elements in another, leftovers ascending. Teaches custom keys instead of comparators.
Hint
Key each element by (rank[x], x) where rank is its index in the second array, or len(arr2) if absent.
4. Largest Number (LeetCode 179) — arrange non-negative integers to form the largest concatenated number. Teaches designing a comparator and proving it is transitive.
Hint
Put a before b if a + b > b + a as strings. The non-obvious part is that this relation is a strict weak ordering; it is, because comparing a+b with b+a is equivalent to comparing the fractions .
Solution
from functools import cmp_to_key
def largest_number(nums: list[int]) -> str:
strs = [str(x) for x in nums]
strs.sort(key=cmp_to_key(lambda a, b: (b + a > a + b) - (b + a < a + b)))
out = "".join(strs)
return "0" if out[0] == "0" else out
assert largest_number([10, 2]) == "210"
assert largest_number([3, 30, 34, 5, 9]) == "9534330"
assert largest_number([0, 0]) == "0"
assert largest_number([432, 43243]) == "43243432"
print("ok")
comparisons, each for -digit numbers. The comparator returns consistently, so any correct sort works; a sloppy one that returns only would trip Java's contract check.
5. Merge k Sorted Lists (LeetCode 23) — merge sorted linked lists. Teaches the heap-based -way merge, exactly phase 2 of external sort.
Hint
Heap of (value, list index, node); the index breaks ties so nodes are never compared.
Solution
import heapq
class ListNode:
def __init__(self, val: int = 0, nxt: "ListNode | None" = None):
self.val, self.next = val, nxt
def merge_k_lists(lists: list["ListNode | None"]) -> "ListNode | None":
heap = [(node.val, i, node) for i, node in enumerate(lists) if node]
heapq.heapify(heap)
dummy = tail = ListNode()
while heap:
_, i, node = heapq.heappop(heap)
tail.next = tail = node
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
def build(xs):
head = None
for x in reversed(xs):
head = ListNode(x, head)
return head
def to_list(node):
out = []
while node:
out.append(node.val)
node = node.next
return out
assert to_list(merge_k_lists([build([1, 4, 5]), build([1, 3, 4]), build([2, 6])])) == [1, 1, 2, 3, 4, 4, 5, 6]
assert merge_k_lists([]) is None and merge_k_lists([None]) is None
print("ok")
time for total nodes, heap space.
6. Distinct Numbers (CSES 1621) — count distinct values among up to integers. Teaches sort-then-scan, and why a Java solution sorting int[] can be attacked (dual-pivot quicksort before JDK 14 had adversarial inputs) while Integer[]/Timsort or shuffling first is safe.
Hint
Sort, count positions where a[i] != a[i-1]. In Java, shuffle before Arrays.sort(int[]) if the judge has anti-quicksort tests.
7. Sort List (LeetCode 148) — sort a linked list in time and extra space. Teaches bottom-up merge sort over runs — Timsort's merging without random access.
Hint
Bottom-up: merge sublists of size 1, 2, 4, … in passes; no recursion stack.
8. Maximum Gap (LeetCode 164) — largest difference between successive elements in sorted order, in linear time. Teaches when to leave comparison sorting behind (radix or the pigeonhole bucket argument).
Hint
With values spanning , the maximum gap is at least ; use buckets of that width and only compare bucket boundaries.
9. Reverse Pairs (LeetCode 493) — count pairs with . Teaches counting during the merge step of merge sort (the same machinery as counting inversions).
Hint
Before merging two sorted halves, sweep a pointer through the right half for each left element; both pointers only move forward.
Solution
def reverse_pairs(nums: list[int]) -> int:
def sort_count(lo: int, hi: int) -> int:
if hi - lo <= 1:
return 0
mid = (lo + hi) // 2
count = sort_count(lo, mid) + sort_count(mid, hi)
j = mid
for i in range(lo, mid):
while j < hi and nums[i] > 2 * nums[j]:
j += 1
count += j - mid
nums[lo:hi] = sorted(nums[lo:hi]) # Timsort merges the two sorted halves in O(n)
return count
return sort_count(0, len(nums))
assert reverse_pairs([1, 3, 2, 3, 1]) == 2
assert reverse_pairs([2, 4, 3, 5, 1]) == 3
assert reverse_pairs([]) == 0
assert reverse_pairs([-5, -5]) == 1
print("ok")
: the sweep is linear per level, and sorted on two concatenated sorted halves is a single Timsort merge — two runs detected, one merge — so it is per level too. This is a nice place to use Timsort's adaptivity.
10. Find K Pairs with Smallest Sums (LeetCode 373) — from two sorted arrays, list the pairs with the smallest sums. Teaches a lazy -way merge: each row nums1[i] + nums2[*] is a sorted run, and you only ever need the head of each.
Hint
Seed the heap with (nums1[i] + nums2[0], i, 0) for the first rows; when you pop (i, j) push (i, j + 1). .
11. Count of Smaller Numbers After Self (LeetCode 315) — for each element, how many later elements are smaller. Teaches stable merge with index tracking — stability is what makes the count correct for duplicates.
Hint
Merge sort indices by value; when an element from the left half is emitted, add the number of right-half elements already emitted. Equal values must emit left first (stability), or duplicates get miscounted.
Solution
def count_smaller(nums: list[int]) -> list[int]:
n = len(nums)
counts = [0] * n
idx = list(range(n))
def sort(lo: int, hi: int) -> None:
if hi - lo <= 1:
return
mid = (lo + hi) // 2
sort(lo, mid)
sort(mid, hi)
merged, i, j = [], lo, mid
while i < mid or j < hi:
# take from the left on ties: equal values are not "smaller"
if j == hi or (i < mid and nums[idx[i]] <= nums[idx[j]]):
counts[idx[i]] += j - mid
merged.append(idx[i])
i += 1
else:
merged.append(idx[j])
j += 1
idx[lo:hi] = merged
sort(0, n)
return counts
assert count_smaller([5, 2, 6, 1]) == [2, 1, 1, 0]
assert count_smaller([-1, -1]) == [0, 0]
assert count_smaller([2, 0, 1]) == [2, 0, 0]
assert count_smaller([]) == []
print("ok")
time, space. Change <= to < and [-1, -1] returns [1, 0] — the stability bug in one character.
12. Smallest Range Covering Elements from K Lists (LeetCode 632) — find the smallest range that contains at least one number from each of sorted lists. Teaches the -way merge heap as a sweep: the heap holds one head per list, and the range is [heap min, current max].
Hint
Push each list's first element and track the maximum pushed. Pop the minimum, update the best range with [min, max], push the next element of that list (updating max); stop when a list runs out. .
Design exercise (no judge). Size an external sort for a file 100× your RAM: runs, fan-in, passes, temp disk, open-file limit, and whether replacement selection saves a pass — using the I/O cost formula. This is the follow-up interviewers ask after any of the problems above.
Common mistakes & interview follow-ups
"Is Python's sort stable? Java's? C++'s?" Python: yes, guaranteed. Java: yes for objects (Timsort), the question is meaningless for primitives (dual-pivot quicksort). C++: std::sort no, std::stable_sort yes. JavaScript: yes since ES2019. Rust: sort yes, sort_unstable no. Go: sort.Sort no, sort.Stable yes.
"Why doesn't Java use Timsort for int[] too?" Stability is unobservable for primitives, and quicksort variants are faster on them — no comparator calls, better cache behaviour, no buffer. Objects need stability (records with equal keys are distinguishable) and their comparisons are expensive, which is Timsort's sweet spot.
"Sort 10 GB with 1 GB of RAM." External merge sort: about 10 (or ~5 with replacement selection) sorted runs, then one 10-way heap merge — two passes, 40 GB of sequential I/O. Mention buffer sizes, temp disk space, and that with very little memory you would merge in multiple passes.
"What if the data is nearly sorted?" Use an adaptive sort (Timsort: close to ); if each element is at most positions from its final place, a size- min-heap sorts it in — Sort a K-sorted array is the classic exercise.
"What can go wrong with a custom comparator?" Non-transitivity, <= instead of < (C++ UB), subtraction overflow, NaN, mutating keys during the sort, random comparators for shuffling. In Java, Timsort may throw "Comparison method violates its general contract!".
"How do databases sort more data than fits in memory?" Sort runs within work_mem, spill them, -way merge; for LIMIT k, a top- heap; for already-ordered input, an index scan avoids the sort entirely; PostgreSQL 13+ can do an incremental sort when the input is sorted on a prefix of the requested keys.
Quick quiz
1. Why does Timsort treat only strictly descending sequences as descending runs?
Answer
Descending runs are reversed in place. If a descending run contained equal elements, reversing it would swap their relative order and break stability. With strictness, equal neighbours end a descending run (they start an ascending one instead), so reversal never reorders equal elements.
2. A machine has 2 GB of memory for sorting and uses 2 MB buffers. How many passes does it need to sort 1 TB, and how much data is transferred in total?
Answer
Runs: . Fan-in: . Since , one merge pass suffices: 2 passes total, TB transferred (each pass reads and writes the whole terabyte).
3. What did de Gouw et al. find wrong with Timsort in 2015, and what were the two different fixes?
Answer
The merge-collapse routine checked the run-length invariant only on the top three stack entries, but merges could create violations deeper down, so the stack could grow beyond its preallocated size (crashing Java with an ArrayIndexOutOfBoundsException on crafted inputs). CPython fixed the rule (also check the fourth entry from the top); OpenJDK enlarged the preallocated stack to cover the worst case reachable with the flawed rule.
4. Why is [](int a, int b) { return a <= b; } dangerous with std::sort, while the equivalent Python key-based sort is not?
Answer
<= is not a strict weak ordering (it is reflexive), which makes std::sort undefined behaviour; libstdc++'s unguarded insertion sort relies on the comparator returning false for equal elements to stop scanning and can run off the array. Python sorts with __lt__ on keys and never trusts the comparator for memory safety; an inconsistent ordering only produces a wrong permutation.
5. Replacement selection produces runs of about on random input. What does it produce on sorted input, on reverse-sorted input, and why?
Answer
Sorted input: a single run — every newly read item is the last output, so it always joins the current run. Reverse-sorted input: runs of exactly — every new item is smaller than the last output, so it is always tagged for the next run, and each run consists of exactly the items in the heap when it started.
Further reading / sources
- Tim Peters,
Objects/listsort.txtin the CPython source — the design document for Timsort (2002) and, since 3.11, its Powersort merge policy. - Stijn de Gouw, Jurriaan Rot, Frank S. de Boer, Richard Bubel, Reiner Hähnle, "OpenJDK's java.utils.Collection.sort() Is Broken: The Good, the Bad and the Worst Case", Computer Aided Verification (CAV 2015), LNCS 9206.
- J. Ian Munro and Sebastian Wild, "Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs", ESA 2018 (Powersort).
- Sam Buss and Alexander Knop, "Strategies for Stable Merge Sorting", SODA 2019 — the analysis of Timsort's merge policy.
- Orson R. L. Peters, "Pattern-defeating Quicksort", arXiv:2106.05123 (2021).
- David R. Musser, "Introspective Sorting and Selection Algorithms", Software: Practice and Experience 27(8), 1997.
- Stefan Edelkamp and Armin Weiß, "BlockQuicksort: Avoiding Branch Mispredictions in Quicksort", ESA 2016.
- Sebastian Wild and Markus E. Nebel, "Average Case Analysis of Java 7's Dual Pivot Quicksort", ESA 2012.
- M. Douglas McIlroy, "A Killer Adversary for Quicksort", Software: Practice and Experience 29(4), 1999.
- Simon Zünd, "Getting things sorted in V8", V8 blog, September 2018.
- Rust 1.81.0 release announcement — the driftsort/ipnsort switch and the panic-on-invalid-
Ordnote. - Donald E. Knuth, The Art of Computer Programming, Vol. 3, 2nd ed. — §5.4 "External Sorting", §5.4.1 replacement selection and the snowplow.
- Alok Aggarwal and Jeffrey S. Vitter, "The Input/Output Complexity of Sorting and Related Problems", Communications of the ACM 31(9), 1988.
- Jeffrey Dean and Sanjay Ghemawat, "MapReduce: Simplified Data Processing on Large Clusters", OSDI 2004.
- PostgreSQL documentation, "Resource Consumption" (
work_mem) and "Using EXPLAIN"; PostgreSQL 15 release notes (balanced k-way merge). - Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 4th ed. — Chapter 6 (heapsort), Chapter 7 (quicksort), Chapter 8 (the comparison lower bound).
Lessons: previous — Non-Comparison Sorts · next — Binary Search Mastery · module — Searching & Sorting · course map.
Related Archon pages: Merge Sort · Quick Sort · Heap Sort · Heaps & Priority Queues · Query Planning & Optimization · Storage Engines · How Databases Work · Sorting & Searching overview.