Draft:Powersort

Powersort

Powersort

Class	Sorting Algorithm
Data structure	Array
Worst-case performance	O(nlogn)
Worst-case space complexity	O(n)

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.

Algorithm Overview

A merge policy is an order to do binary merges (one pair of adjacent runs in each step) that eventually produces a big sorted list. It can always be represented by a binary tree. The merge cost of an execution is the sum of all produced runs.

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.

Powersort in action. The “power” of a run boundary corresponds to how deep the blue line can sink down, connecting the midpoints of the two runs, before it “hits” a node of the imaginary, green perfectly balanced binary search tree. Illustration from PyCon US 2023 talk by Sebastian Wild.

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[s1..e1) is leftmost run
    while e1 < n
        b2 := e1 + 1;  e2 := FirstRunOf(A[b2..n)) 
        // A[s2..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, n)
    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

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 `ab2269f3c0ca0265b4ff462f1bda29442182de11`, 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.

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 forth rule to Timsort, but required two major patches of OpenJDK. While eventually successful, the correctness proof of Timsort's stack height and the running-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, it's 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

Example merge tree for Powersort (top) and 4- way Powersort (bottom) for an input of size n = 16.

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(A[0..n))
    S := empty stack  // capacity (k − 1)⌈logk(n) + 1⌉
    b1 := 0;  e1 = FirstRunOf(A[b1..n))
    while e1 < n
        b2 := 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

• Practical hands-on experience with Powersort can be gained by playing Powersort's Pursuit.
• A more graphical approach to explaining Powersort is used in Sebastian Wild's PyCon US 2023 talk.

References

This page will be placed in the following categories if it is moved to the article namespace.

Categories:

• Articles with example pseudocode
• Comparison sorts
• Divide-and-conquer algorithms