Timsort: Run Detection and Galloping Merge

The problem: real data is not random

Classic complexity analysis assumes worst-case, adversarial input. Real-world arrays are almost never random: log timestamps arrive nearly sorted, a database index gets a few rows appended, a merged dataset is a concatenation of already-sorted chunks. A plain merge sort ignores this and always does its full ~n·log₂n comparisons; quicksort can even degrade to O(n²) on such structured input.

Timsort's premise is that partially-ordered input should cost less than random input. An algorithm with this property is called adaptive, and the standard formal target is to run in O(n + n·log(n/r)) time, where r is the number of natural runs — dropping to O(n) when the data is one long run. Tim Peters designed it for CPython's list.sort(), where two extra requirements were non-negotiable:

• Stability — equal elements must keep their original order (Python sorts tuples, dicts, records by key).
• Few comparisons — in Python each comparison is an expensive dynamic dispatch, so minimizing comparison count matters as much as minimizing swaps.

How it works, step by step

Timsort processes the array left to right using an explicit stack of pending runs.

1. Compute minrun. Pick minrun in [32, 64] from the array length n so that n/minrun is at or just below a power of two — this keeps the eventual merges balanced. (It takes the top 6 bits of n and adds 1 if any lower bit is set.)
2. Detect a run. Starting at the current index, scan the longest ascending (a ≤ b ≤ c) or strictly descending (a > b > c) contiguous run. A descending run is reversed in place — strict descent is required so the reversal stays stable.
3. Extend to minrun. If the natural run is shorter than minrun, grab the next elements and use binary insertion sort to extend it to minrun length.
4. Push and maybe merge. Push the run onto the stack, then enforce the merge invariants below by merging adjacent runs. When Timsort merges, it uses galloping mode to skip runs of consecutive winners.

The stack invariants (for run lengths A, B, C from the top) are: A > B + C and B > C. Whenever a new push violates them, Timsort merges to restore balance, which bounds the stack to O(log n) entries.

Complexity and a worked trace

Bounds: best case O(n) (input is already sorted — one run, no merges); average and worst case O(n log n); auxiliary space O(n), though the temp buffer needed for any single merge is at most the size of the smaller run, so effectively ≤ n/2. It is stable and does O(n) comparisons on already-sorted data.

Galloping: during a merge of runs X and Y, if one run wins MIN_GALLOP = 7 comparisons in a row, Timsort switches to galloping: it uses exponential + binary search to find how many elements of the winning run precede the other run's next element, copying that whole block at once. A block of k winners then costs O(log k) comparisons instead of k. If galloping stops paying off, MIN_GALLOP is nudged up and normal merging resumes.

input:  [5,4,3,  7,8,9,  1,2,6]     minrun ~ 3
run 1:  5 4 3   (descending) -> reverse -> 3 4 5
run 2:  7 8 9   (ascending)                7 8 9
run 3:  1 2 6   (ascending)                1 2 6
merge 3&2 -> 1 2 6 7 8 9
merge with 1 -> 1 2 3 4 5 6 7 8 9

Where it is used in real systems

Timsort is arguably the most-deployed sorting algorithm on Earth, because it sits under several language runtimes:

• Python — list.sort() and sorted() since 2002 (CPython 2.3); the canonical implementation.
• Java — Arrays.sort() for object arrays and Collections.sort() since Java 7 (a port of Peters' C code). Primitive arrays use a dual-pivot quicksort instead because stability is irrelevant for primitives.
• Android — the Java runtime's default object sort, so effectively every Android app.
• Rust — slice::sort() (the stable sort) is a Timsort-derived driftsort/adaptive mergesort.
• JavaScript — V8 (Chrome, Node.js) made Array.prototype.sort a Timsort in 2018 to guarantee stability required by the ES2019 spec.
• Swift — the standard library's sort() uses a Timsort-style stable adaptive merge.

The common thread: these are general-purpose library sorts where stability and good behavior on structured input matter more than raw cache-friendliness on random arrays.

Compared to the alternatives

The right way to place Timsort is by what it trades away and what it buys.

• vs. plain merge sort: same O(n log n) worst case and same stability, but Timsort is adaptive — it exploits existing runs and gallops through skewed merges, so on partially-ordered data it does far fewer comparisons and drops to O(n) on sorted input. The cost is a considerably more intricate implementation.
• vs. quicksort / introsort: quicksort is usually faster on random data and sorts nearly in place (O(log n) stack), but it is not stable and its naive form is O(n²) on adversarial input. Timsort trades some raw speed and O(n) memory for stability, adaptivity, and a guaranteed O(n log n) ceiling.
• vs. heapsort: heapsort is O(1) space and O(n log n) worst case but is not stable, not adaptive, and cache-unfriendly.

The core tradeoff: Timsort spends O(n) auxiliary memory and code complexity to guarantee stability plus best-in-class performance on the ordered-ish data that real programs actually feed a sort.

Pitfalls, a famous bug, and significance

The 2015 invariant bug. In 2015 a team using the Java verification tool KeY (de Gouw et al.) proved that the run-merging invariants, as implemented, did not actually guarantee the merge stack stayed small — a crafted adversarial input could overflow the fixed-size runLen array and throw ArrayIndexOutOfBoundsException. The bug had lain dormant in Python, Java, and Android for over a decade. The fix: either enlarge the stack bound or, more robustly, check two invariants deeper (compare A>B+C and B>C plus the run below). Python patched it; Java initially just enlarged the array.

Other pitfalls: the O(n) temp buffer makes it unsuitable for hard memory-constrained embedded contexts; on truly random data it can be modestly slower than an in-place quicksort; and getting the descending-run reversal right (strict >, not ≥) is essential to preserving stability.

Significance: Timsort mainstreamed the idea that a production sort should be measured on real, structured inputs — and it remains the default in most major languages more than two decades later.

Timsort versus other general-purpose comparison sorts

Algorithm	Best	Average	Worst	Space	Stable	Adaptive
Timsort	O(n)	O(n log n)	O(n log n)	O(n)	Yes	Yes
Merge sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes	No
Quicksort (Hoare/introsort)	O(n log n)	O(n log n)	O(n²) / O(n log n)	O(log n)	No	No
Heapsort	O(n log n)	O(n log n)	O(n log n)	O(1)	No	No
Binary insertion sort	O(n)	O(n²)	O(n²)	O(1)	Yes	Yes