Timsort

TimSort is a stable, hybrid sorting algorithm derived from merge sort and insertion sort. It was designed by Tim Peters in 2002 for the PyPy project and was later adopted as the default sorting algorithm in CPython for list.sort and the built-in sorted function. TimSort is optimized for real-world data that often contain ordered subsequences, or runs.

The algorithm operates by identifying runs, which are contiguous subsequences that are already ordered. It scans the input to find increasing runs (and short decreasing runs, which are reversed to become increasing). Short runs are extended to a minimum run length using binary insertion sort. Each identified run is pushed onto a stack, and neighboring runs are merged according to specific invariants to maintain efficiency. During merges, a galloping mode is used to accelerate the process when one run dominates the other, improving performance on certain patterns.

TimSort guarantees O(n log n) worst-case time and is stable, meaning equal elements preserve their relative order. It is adaptive, performing closer to linear time on inputs that already contain ordered runs. The algorithm requires O(n) extra space for temporary storage during merges.

Adoption and impact: TimSort has become the de facto standard sort in Python, powering list.sort and sorted. It has also been adopted by other libraries and languages, including the Java standard library for sorting Object arrays, where it provides a stable sort for non-primitive types. TimSort has influenced the design of sorting routines in multiple ecosystems due to its practical performance on real-world data.