Powersort

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 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 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 stable and comparison based. This property is essential for many applications. Powersort was proposed by J. Ian Munro and Sebastian Wild.

Overview Powersort is a stable mergesort variant that adapts to existing runs in the input data, i.e., ranges in the input that are already in order. It maintains a stack of runs yet to be merged and alternates between finding the next run and merging adjacent runs near the top of the run stack. This non-recursive mode of operation is particularly cache-friendly.

Like Timsort, it enforces a minimal run length by “filling up” short runs using insertion sort up to a chosen minimal run length. Each merge step combines two adjacent runs into a single one using a “galloping strategy”: exponential search is used to find the prefix of one run that precedes the minimum in the other run. This can save comparisons compared to a traditional linear merge. Powersort improves Timsort in terms of the merge policy, i.e., the rule(s) that decides which runs on the run stack are merged before proceeding. Timsort's original policy used a suboptimal heuristic based solely on the lengths of runs; Powersort replaces this with a rule simulating Mehlhorn's algorithm for computing nearly optimal binary search trees with low overhead, thereby achieving optimal adaptivity up to an additive linear term. The pseudocode below shows a simplified Powersort implementation.

algorithm PowerSort(A[0..n)) S := stack of runs // capacity ⌈lg(n)⌉ + 1 b1 := 0; e1 := FirstRunOf(A[b1..n)) // A[b1..e1) is leftmost run while e1 < n b2 := e1 + 1; e2 := FirstRunOf(A[b2..n)) // A[b2..e2) next run P := NodePower(n, b1, e1, b2, e2) while S.top().power > P (b1, e1) := Merge(S.pop(), A[b1..e1)) end while S.push((A[b1, e1), P)); b1 := b2; e1 := e2 end while // Now A[b1..e1) is the rightmost run while ¬S.empty() (b1, e1) := Merge(S.pop(), A[b1..e1)) end while

algorithm NodePower(n, b1, e1, b2, e2) n1 := e1 − b1; n2 := e2 − b2; a := (b1 + n1/2)/n; b := (b2 + n2/2)/n p := 0 while ⌊a · 2p⌋ == ⌊b · 2p⌋ p := p + 1 end while return p

The implementation of Merge is inherited from TimSort and includes the "galloping" heuristic.

Adoption The implementation of Powersort in CPython began with version 3.11, replacing the older Timsort algorithm. The change was motivated by Powersort's superior performance and stability. The core implementation can be found in the CPython source code within the listobject.c file, where the list-sorting functions are defined. The detailed merge policies and algorithm are described in listsort.txt... The transition to Powersort involved addressing issue #78742 in the CPython repository. The PyPy project, known for its high-performance Just-In-Time (JIT) compiler for Python, also integrated Powersort. The relevant commit, identified as 6d2f7a78baa8d4d2f94f5fb709f697a560b45f4e, details the inclusion of Powersort into PyPy's list-sorting functions. In AssemblyScript, Powersort was integrated to enhance the performance of WebAssembly applications. The relevant pull request, #1904, and the implementation details can be found in the sort.ts file within the AssemblyScript standard library. These implementations across different platforms highlight the adaptability and efficiency of Powersort in various programming environments.

Implementations As with TimSort, the full implementation of Powersort is hundreds of lines and too large to fit in a Wikipedia article. Readers are advised to consult the following sources:

C implementation from CPython version 3.13.5. Starts on line 1577 and ends on line 3151, for a total of 1574 lines (974 excluding comments and blank lines). Python implementation from PyPy 3.11 version 7.3.19. 680 lines (434 excluding comments and blank lines). This code still uses the name "TimSort", but the merge strategy has been changed to "powersort".

… excerpt ends here. Continue reading the full article.