271. What is Timsort and why do Python and Java use it?
MediumSorting
Show model answer
Timsort is a hybrid of merge sort and insertion sort designed for real data, which often contains ordered stretches. It scans for natural runs (ascending, or strictly descending runs that it reverses), extends short runs to a minimum length (typically 32–64) with binary insertion sort, and pushes runs on a stack, merging them while maintaining size invariants that keep merges balanced.
Merges use "galloping": when one run keeps winning, it switches to exponential search to copy whole blocks at once. The result is stable, O(n) on already sorted or reverse-sorted input, O(n log n) worst case, with O(n) extra space. Python’s `sorted`, Java’s object sort and Android use it, while Java sorts primitives with dual-pivot quicksort because stability does not matter there.