Python's sorted() and list.sort() use Timsort (Tim Peters, 2002): a hybrid of merge sort and insertion sort that exploits the order already present in the data. It is stable, O(n log n) in the worst case and O(n) on sorted input. The API itself is described in sorting lists in Python.
How Timsort works
- Runs. The array is scanned for natural runs: non-decreasing or strictly decreasing stretches; a decreasing run is reversed in place.
- minrun. Short runs are extended to
minrun(about 32–64 elements) with binary insertion sort, which is fast on small pieces. - Merge stack. Runs are pushed on a stack and merged by rules that keep run sizes balanced, so the merge tree has depth
O(log n). - Galloping. If one run wins many comparisons in a row during a merge, Timsort switches to an exponential search (gallop) and moves a whole chunk at once.
The result is a stable sort that is close to n on nearly sorted data and n log n otherwise. The picture above is a simplified model.
