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 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 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.

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 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)
S := stack of runs // capacity ⌈lg⌉ + 1
b1 := 0; e1 := FirstRunOf)
// Ab1..e1) is leftmost run
while e1 < n
b2 := e1 + 1; e2 := FirstRunOf)
// A[b2..e2) next run
P := NodePower
while S.top.power > P
:= Merge)
end while
S.push);
b1 := b2; e1 := e2
end while // Now A[b1..e1) is the rightmost run
while ¬S.empty
:= Merge)
end while
algorithm NodePower
n1 := e1 − b1; n2 := e2 − b2;
a := /n; b := /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 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.
  • Python implementation from PyPy3.11 version 7.3.19. 680 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 comparisons, where, for 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 is an extension of Powersort that generalizes the binary merging process to k-way merging. This approach can reduce the number of merge operations and hence reduces the amount of memory transfer. It was proposed by William Cawley Gelling, Markus E. Nebel, Benjamin Smith, and Sebastian Wild in 2023.
Multiway Powersort retains the stability and adaptiveness of the original Powersort algorithm, 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)
S := empty stack // capacity ⌈logk + 1⌉
b1 := 0; e1 = FirstRunOf)
while e1 < n
b2 := e1; e2 := FirstRunOf)
P := Powerk
while S.top.power > P
P':= S.top.power
L := empty list; L.append)
while S.top.power P′
L.append)
end while
// merge runs in L with Ab1..e1)
:= Merge)
end while
S.push)
b1 := b2; e1 := e2
end while // Now A[b1..e1) is the rightmost run
while ¬S.empty
// pop

end while
algorithm Powerk
n1 := e1 − b1; n2 := e2 − b2; p := 0
a := /n; b := /n
while ⌊a · kp⌋ ⌊b · kp⌋
p := p + 1
end while
return p

Further resources