66x faster on sorted data: Timsort, 24 years on

Tim Peters died on July 15, 2026. Guido van Rossum announced it today, November 11, on the Python discussion forum. The sort Peters wrote in 2002 still sorts a million already-ordered integers in 5.6 milliseconds — 66 times faster than the same million shuffled. I re-ran it this afternoon to check the number holds up, and it does.

What happened

Guido's post is short and plain: Tim died "earlier this year on July 15." Peters was Python's second real user after Guido, a core developer from the early 1990s, a Python Software Foundation director from 2001 to 2014, and the author of the Zen of Python (PEP 20) — the poem every Python programmer has seen at least once via import this.

He is also the reason sorted() is fast on the data you actually have. In 2002 he designed Timsort for Python lists. Java adopted it for sorting objects. Android adopted it. It is the default sort in Swift, Rust, and Go's slices package. If you have ever sorted anything in a mainstream language, you have run his code.

The design bet, as Neil Schemenauer put it in the memorial thread, was that Tim "was always thinking of the common case, the favorable case as well as the worst-case scenarios." Real-world data is rarely random: it arrives mostly sorted, in runs, with a few elements out of place. Timsort detects those runs and merges them instead of sorting from scratch.

The measurement

I ran this on CPython 3.12.3, on a small Linux VM, sorting 1,000,000 integers, 9 runs each, median reported:

input                         median     range (9 runs)
sorted                        5.6 ms     5.4 – 11.0 ms
nearly sorted (100 swaps)     7.9 ms     7.7 – 15.0 ms
reversed                      8.0 ms     7.8 – 12.9 ms
random                        369.4 ms   364.6 – 379.6 ms

Sorted input is 66x faster than random input. A hundred random swaps in a million elements cost almost nothing — 7.9 ms against 5.6. And the result that surprised me most when I first saw it: reversed input takes 8.0 ms, not 369. A reversed list is one descending run, and Timsort reverses it in place for free.

The sorted times bounce around (5.4 to 11.0 ms across runs) because at that speed the measurement is mostly VM noise. The random times don't — 364 to 380 ms, tight. The gap is real, not a fluke of one lucky run.

To show the mechanism rather than just the clock, I wrapped the integers in a class that counts comparisons, at n = 100,000:

input                         comparisons     wall time
sorted                        99,999          24.7 ms
nearly sorted (10 swaps)      101,106         25.8 ms
reversed                      99,999          25.0 ms
random                        1,529,183       444.8 ms

For reference, n log2 n at n = 100,000 is 1,660,964.

99,999 comparisons on a sorted list of 100,000 elements is n − 1 — the theoretical minimum. You cannot confirm a list is sorted with fewer comparisons than that. Timsort does exactly the minimum and then stops. Random input costs 1.53 million comparisons, close to the n log2 n bound. The counted runs are slower in wall time than the raw-int runs because every comparison goes through Python-level __lt__, but the comparison counts are the point: the adaptivity is in the algorithm, not the hardware.

Why this one still matters

Sorting is the most-solved problem in computer science, and the textbook answer — n log n, worst case, done — would have been fine. Peters' move was to notice that the textbook's worst case is not the common case, and to build the common case into the algorithm. That is the Zen of Python as engineering: "Special cases aren't special enough to break the rules. Although practicality beats purity." Timsort is a practicality-beats-purity algorithm, shipped as the default.

It is also worth saying plainly what the memorial thread kept saying: Peters did the unglamorous work. He polished pymalloc, the dict implementation, the cyclic garbage collector — the parts of Python nobody notices until they break. Timsort is the one piece of that work with his name on it, and it is in every Python program that has ever called sorted().

Run import this today and the first line is still his. The sort still runs 66x faster on the data you actually have. That is a reasonable epitaph for a programmer: the code is still doing the job, and it is still doing it well.

Sources: Guido van Rossum, "In Memoriam: Tim Peters 1952–2026," discuss.python.org, November 11, 2026 (death July 15, 2026; Timsort 2002, adopted by Java and Android; PSF director 2001–2014; PEP 20); the timing and comparison counts are my own runs on CPython 3.12.3, n = 1,000,000 for wall time (9 runs, median) and n = 100,000 for comparison counts (3 runs, median).