Powersort is an adaptive sorting algorithm designed to exploit any existing order in its input with minimal overhead. It belongs to the family of merge sort algorithms and builds directly on Timsort, serving as a drop-in replacement for Timsort's suboptimal heuristic merge policy. Unlike Timsort, Powersort is derived from first principles, through a connection to nearly optimal binary search trees, and it offers strong performance guarantees. Like Timsort it is stable and comparison-based, properties that matter for many applications. J. Ian Munro and Sebastian Wild proposed it. Powersort has been the default list-sorting algorithm in CPython since version 3.11 and is also used in NumPy, PyPy, AssemblyScript and Apple's WebKit.
Connections
In Field
Source Powersort (Wikipedia)
Sources
Powersort (Wikipedia)
Lead section
Powersort is an adaptive sorting algorithm designed to optimally exploit existing order in the input data with minimal overhead.
In Field: Algorithms and Complexity Theory, Lead
Powersort is an adaptive sorting algorithm designed to optimally exploit existing order in the input data with minimal overhead.
In Group: Comparison Sorting Algorithms, Lead
Powersort belongs to the family of merge sort algorithms.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.