Tim Sort

Tim Sort is the sort algorithm running inside Python's list.sort() and sorted(), Java's Arrays.sort(Object[]) and Collections.sort(), V8's Array.prototype.sort() (since Node 11), Android's standard library, and Swift's Array.sort(). If you have ever called a "sort" function in those languages on object arrays, you have used Tim Sort.

It was designed by Tim Peters in 2002 specifically for Python's needs: stable, fast on real-world (often partially sorted) data, in-place where reasonable, and graceful on adversarial inputs. The algorithm is a hybrid of merge sort and insertion sort with a long list of practical optimizations that exploit pre-existing order in the input.

The core insight that drives the algorithm: real-world arrays are rarely random. They contain runs (already-sorted subsequences), and a sort algorithm that detects and merges runs instead of starting from scratch does less work.

This chapter explains the algorithm, the run-detection and merging machinery, why it is stable and adaptive, and a simplified educational implementation. Production implementations (Python's listsort.c, JDK's TimSort.java) run to around 1000 lines and build on the simplified version below.