Powersort

Common card · No. 368422

Powersort is an adaptive sorting algorithm designed to optimally exploit existing order in the input data with minimal overhead. Powersort is the default list-sorting algorithm in CPython since version 3.11 and is also used in NumPy, PyPy, AssemblyScript, and Apple's WebKit. Powersort belongs to the family of merge sort algorithms. More specifically, Powersort builds on Timsort; it is a drop-in replacement for Timsort's suboptimal heuristic merge policy. Unlike Timsort, Powersort is derived from first principles (see connection to nearly optimal binary search trees) and offers strong performance guarantees. Like Timsort, Powersort is stable and comparison-based. This property is essential for many applications. Powersort was proposed by J. Ian Munro and Sebastian Wild.

Read on Wikipedia