Powersort
| Class | Sorting algorithm |
|---|---|
| Data structure | Array |
| Worst-case performance | O(nlogn) |
| Worst-case space complexity | O(n) |
| Optimal | No; "near-optimal", but be beaten by a more advanced version of galloping |
Powersort is an adaptive sorting algorithm designed to optimally exploit existing order in the input data with minimal overhead. Since version 3.11, Powersort is the default list sorting algorithm in CPython and is also used in PyPy and AssemblyScript. 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 the latter, it is derived from first principles (see connection to nearly optimal binary search trees) and offers strong performance guarantees.
Like Timsort, Powersort is a stable sort and comparison-based.This property is essential for many applications. Powersort was proposed by J. Ian Munro and Sebastian Wild.