Powersort

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 2 := 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 file, where the list-sorting functions are defined. The detailed merge policies and algorithm are described in ... 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 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 PyPy3.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". == Comparison with Timsort ==

Timsort's original merge policy caused several problems before being replaced by Powersort. First, as accidentally observed during the formal verification of Timsort, Tim Peters's original formulation did not guarantee the desired height bound for the run stack, leaving both CPython and OpenJDK vulnerable to a stack overflow. This was eventually fixed by adding a fourth rule to Timsort but required two major patches of OpenJDK. While eventually successful, the correctness proof of Timsort's stack height and the run-time analysis are very complicated. Further, it was discovered that Timsort's merge policy also has a performance blind spot: specific patterns of run lengths cause Timsort to repeatedly perform very unbalanced merges, resulting in asymptotically 50% overhead. Powersort simultaneously removes all of these limitations. Despite its advanced theoretical foundation, its analysis is much easier, and it provably never uses more than n\mathcal{H} +O(n) comparisons, where \mathcal{H} = \sum_{i=1}^{r} \frac{\ell_i}{n} \log_2\left({\frac n{\ell_i}}\right), for \ell_1,\ldots,\ell_r the lengths of the runs in the input. Powersort has been shown to outperform Timsort by up to 30% on certain types of input data that contain long runs of sorted elements. Powersort has further been extended to multiway merging, something that was not possible with Timsort. == Multiway Powersort ==

Multiway Powersort and is just as easy to analyze. The key differences to normal Powersort are: • The computation of powers uses the basis k instead of 2. • When merging runs, we have to pop all runs from the stack that are tied in power with the topmost run. Details are shown in the pseudocode below. algorithms k-wayPowerSort(A[0..n)) S := empty stack // capacity (k − 1)⌈logk(n) + 1⌉ b1 := 0; e1 = FirstRunOf(A[b1..n)) while e1 2 := e1; e2 := FirstRunOf(A[b2..n)) P := Powerk(n, b1, e1, b2, e2) while S.top().power > P P':= S.top().power L := empty list; L.append(S.pop()) while S.top().power == P′ L.append(S.pop()) end while // merge runs in L with A[b1..e1) (b1, e1) := Merge(L, 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() // pop (up to) k − 1 runs, merge with A[b1..e1) (b1, e1) := Merge(S.pop(k − 1), A[b1..e1)) end while algorithm Powerk(n, b1, e1, b2, e2) n1 := e1 − b1; n2 := e2 − b2; p := 0 a := (b1 + n1/2)/n; b := (b2 + n2/2)/n while ⌊a · kp⌋ == ⌊b · kp⌋ p := p + 1 end while return p == Further resources ==

• A playful way to understand merge policies is the game Powersort's Pursuit. • A more graphical approach to explaining Powersort is used in Sebastian Wild's PyCon US 2023 talk. == References ==