Tim Sort Explained

Real data is rarely random — it usually contains runs, sequences that are already ascending or descending. Tim Sort scans the array for these natural runs, reverses descending ones, and treats them as pre-sorted building blocks. Short runs are extended to a minimum length using Insertion Sort.

1) Identify runs and use Insertion Sort to bring each up to a minimum run length (typically 32-64). 2) Push runs onto a stack and merge them using a carefully tuned set of invariants that keep merges balanced. 3) Galloping mode accelerates merges when one run is consistently smaller, skipping ahead in big jumps.

Tim Sort is stable, achieves O(n) on already-sorted data, and guarantees O(n log n) worst case with O(n) space. It combines Insertion Sort's speed on small/ordered data with Merge Sort's reliability. Because real inputs are so often partially sorted, Tim Sort routinely beats pure Quick Sort or Merge Sort on practical workloads — which is why language designers chose it as the default.