Powersort

What is Powersort?

Powersort is a natural run-based mergesort algorithm with provably near-optimal merge cost. It was designed by J. Ian Munro and Sebastian Wild and presented at ESA 2018. In Python 3.11, it replaced Timsort's merge policy in CPython, and it is also widely used beyond CPython (including Apple's WebKit, PyPy and NumPy).

📈

Adaptive to Existing Order

Exploits existing order present in the data, requiring far fewer comparisons on partially-sorted inputs.

⚡

Provably Nearly Optimal

Its mathematically grounded node-power merge policy builds merge trees with provable merge cost at most n · H + 2n — sorting with n · H + 3n ≤ n log₂ n + O(n) comparisons, where H is the run-length entropy of the input.

🐍

Python 3.11 Default

Adopted in CPython 3.11 as a drop-in improvement over Timsort's original merge strategy, with zero API changes for users.

How the Algorithm Works

Like Timsort, Powersort scans the input for natural runs — maximal ascending (or reversed-descending) ranges. The innovation is in how those runs are merged: instead of Timsort's stack-based heuristic, Powersort uses a carefully computed run-boundary power to schedule merges in a near-optimal order.

import math

def power(run1, run2, n):
    i1 = run1[0]; n1 = run1[1]
    i2 = run2[0]; n2 = run2[1]
    assert n1 >= 1 and n2 >= 1
    assert i1 >= 0 and i2 == i1 + n1 and i2 + n2 <= n
    a = (i1 + n1/2) / n
    b = (i2 + n2/2) / n
    l = 0
    while math.floor(a * 2**l) == math.floor(b * 2**l):
        l += 1
    return l

Comparison with Timsort merge policy

🪲 Timsort's troubled merge policy

Part of the reason why Powersort was so welcomed is the troublesome history of Timsort's original merge policy, which has been a source of bugs and confusion in both Python and Java implementations. For many years, the standard library sorting methods were susceptible to a stack overflow from adversarial inputs!

While Timsort was eventually patched, Powersort's mathematically grounded merge policy elegantly resolves this issue from first principles, making the formal proof for correctness and needed stack size robust and intuitive.

Powersort in Python 3.11

Python's built-in list.sort() and sorted() have used Timsort since Python 2.3. With Python 3.11 (released October 2022), the CPython team adopted Powersort's merge strategy, making every Python program that sorts data an implicit beneficiary of this research.

# Python 3.11+ uses Powersort under the hood automatically
import sys
print(sys.version)  # 3.11.x ...

data = [5, 3, 1, 4, 1, 5, 9, 2, 6]
data.sort()       # Powersort at work!
print(data)       # [1, 1, 2, 3, 4, 5, 5, 6, 9]

Implementations & Code

Powersort is used in a growing number of language runtimes, standard libraries, and scientific/systems software. All links below are to open-source code.

Minimal Python sketch

"""
Minimal illustrative Powersort sketch.
For helper functions, see https://tiny.cc/timsort.
"""
import math

def power(run1, run2, n):
    # Compute the "power" of the boundary between run1 and run2 .
    # Input: adjacent runs run1, run2 from a list of total length n.
    # See listsort.txt for details; code follows CPython.
    i1 = run1[0]; n1 = run1[1]
    i2 = run2[0]; n2 = run2[1]
    a = 2 * i1 + n1
    b = a + n1 + n2
    l = 0
    while True:
        l += 1
        if a >= n:
            assert b >= a
            a -= n; b -= n
        elif b >= n:
            break
        assert a < b < n
        a <<= 1; b <<= 1
    return l

def powersort(a, extend_run=extend_run):
    """
    Sort a list using powersort.
    Note: Unlike CPython's version, this variant stores the run-boundary power 
    in the right run. This removes the need for updating powers upon merges.
    """
    n = len(a)
    i = 0
    runs = []  # stack of (start, length, power) tuples
    j = extend_run(a, i)
    runs.append((i, j-i, 0))
    i = j
    while i < n:
        j = extend_run(a, i)
        p = power(runs[-1], (i,j-i), n)
        while p <= runs[-1][2]:
            merge_topmost_2(a, runs)
        runs.append((i,j-i,p))
        i = j
    while len(runs) >= 2:
        merge_topmost_2(a, runs)

Powersort-Based Hybrid Sorts

These implementations don't use Powersort as their whole sorting algorithm, but embed its node-power merge policy as one component inside a larger hybrid design.

Reference & Research Implementations

Not shipped in a production language or library, but built for benchmarking, study, or as a starting point for further ports.

Publications & Further Reading

The following is a curated list of papers, articles, and resources related to Powersort, and its implementations in various frameworks.

Generic Info and Background on Powersort

Algorithmic Variants of Powersort

Enrichment & Fun

On this page, I collect basic information and links about Powersort. I've been doing this on my personal website, but felt it's time to move it to a dedicated site to make it easier to find and explore, and let other contribute to it.