Tim Sort

Tim Peters, 1993

Tim Sort was designed by Tim Peters in 2002 (based on ideas from 1993) for Python's built-in sort. It exploits the fact that real-world data often contains pre-existing ordered subsequences called 'runs'. The algorithm first scans the array to identify natural ascending runs, extending short ones to a minimum run length using insertion sort. It then merges these runs pairwise, similar to merge sort but leveraging the existing order. Used as the default sort in Python, Java, and Android, its O(n log n) worst case and O(n) best case make it exceptionally practical. The visualization highlights discovered runs in alternating teal shades, with gold merge pointers during the merge phase.