listsort.txt, animated
The Timsort Lab
In 2002 Tim Peters replaced Python's sort with a new one and, in his words, "modestly called timsort (hey, I earned it <wink>)". Its trick: real data is rarely random. Timsort hunts for runs that are already in order, merges them like a careful librarian, and switches to galloping when one run keeps winning.
Watch it sort
Run stack (pending runs, bottom → top; Timsort merges neighbours to keep the sizes in balance)
Python uses a minrun between 32 and 64. Then lists under 64 items are a single binary insertion, and you'd never see a merge. The teaching settings use a smaller minrun so the merges and galloping show up on a small screen. The algorithm is otherwise the classic Timsort, with the 2015 merge_collapse fix. Since Python 3.11 CPython picks merge order with Munro and Wild's "powersort" rule; runs, binary insertion and galloping are still Tim's.
The race
Same data, five algorithms, one comparison per tick each. The clock here is comparisons, not seconds. A comparison is the one thing every general-purpose sort has to pay for, and in Python, comparing objects is slow.
The scoreboard: 1,000 items
Comparisons each algorithm needs for 1,000 items on every data shape from listsort.txt. Computed live in your browser, on fresh data each time you press the button. Lowest in each row is green.
Why "stable" matters
A stable sort never reorders items that compare equal. That lets you sort in passes: sort by name, then by house, and each house stays alphabetical. Timsort is stable. Heapsort isn't.