Timsort sorted real-world data by exploiting the order already in it

Sorting algorithms are usually measured on random data, but real lists are rarely random — databases, user interfaces and logs often arrive in nearly sorted chunks. Tim Peters, a Python core developer, designed timsort in 2002 for Python 2.3 on exactly that observation: an adaptive, stable, natural mergesort that finds the runs of order already present and exploits them.

The algorithm walks the array once, left to right, identifying ascending or descending runs; each run is pushed on a stack, and runs are merged whenever they satisfy a size-balance criterion so merges stay cheap. Runs shorter than a minimum length are topped up with insertion sort, which is fast on small arrays. Because the input is never split blindly, partially ordered data can be sorted with as few as N-1 comparisons.

The result replaced Python's previous samplesort hybrid and shipped as the standard list.sort() from Python 2.3. Its practical speed on real-world data made it an export: Java SE 7 adopted it for sorting arrays of objects, Android and GNU Octave use it, the V8 JavaScript engine adopted it, and Swift's sort and Rust's standard library were built on the same idea.

Timsort is stable — equal elements keep their relative order — so it underpins multi-key sorts such as sorting by zip code and then by name. Even a subtle bug found in 2015 in the standard implementations was fixed across Python, Java and Android, evidence of how widely the algorithm had spread.