ZetCode

Python Timsort

last modified November 18, 2026 Python 3.15

In this article we explain Timsort, the sorting algorithm behind Python's list.sort method and the sorted built-in function. We take it apart piece by piece, put the pieces together into a working implementation, and measure how the built-in sort behaves on different kinds of input.

Timsort was written by Tim Peters for Python 2.3 in 2002. It is a hybrid of merge sort and insertion sort that looks for order already present in the data. Java uses it to sort arrays of objects, and the V8 JavaScript engine uses it for Array.prototype.sort.

Timsort algorithm

Timsort walks over the list once from left to right. It finds the next run, a part of the list that is already sorted, and extends short runs with binary insertion sort to a minimum length called minrun. Each run is pushed on a stack, and adjacent runs on the stack are merged according to a merge policy. Merges switch to galloping when one run keeps winning.

PropertyValue
Time, best case (sorted or reversed input)O(n)
Time, average and worst caseO(n log n)
Extra spaceO(n), at most n/2 references for a merge
Stableyes
Adaptiveyes, fewer comparisons on partially ordered data

The algorithm keeps changing. Python 3.11 replaced the original merge rules with the powersort merge policy, Python 3.13 extended the handling of descending runs, and Python 3.15 changed how minrun is computed. The examples in this article follow Python 3.15.

Natural runs

A run is either ascending (non-decreasing) or descending. A descending run is reversed in place, so every run on the stack is ascending.

runs.py
def count_run(vals, lo, hi):
    """Return the end of the run starting at lo; reverse it if descending."""

    end = lo + 1
    if end == hi:
        return end

    if vals[end] < vals[lo]:
        while end < hi and vals[end] < vals[end - 1]:
            end += 1
        vals[lo:end] = reversed(vals[lo:end])
    else:
        while end < hi and not vals[end] < vals[end - 1]:
            end += 1

    return end


def find_runs(vals):
    runs = []
    lo = 0
    while lo < len(vals):
        end = count_run(vals, lo, len(vals))
        runs.append(vals[lo:end])
        lo = end
    return runs


data = [1, 4, 7, 9, 8, 5, 2, 3, 3, 6, 10, 0, 11, 12]
print(data)

for run in find_runs(data):
    print(run)

The count_run function looks at the first two elements to decide the direction of the run. An ascending run continues while the next element is not smaller than the previous one. A descending run continues while the next element is strictly smaller; equal elements end it, because reversing equal elements would break stability. The first run 1, 4, 7, 9 ends at 8. The descending run 8, 5, 2 is reversed to 2, 5, 8. The third run shows that equal elements continue an ascending run.

$ python runs.py
[1, 4, 7, 9, 8, 5, 2, 3, 3, 6, 10, 0, 11, 12]
[1, 4, 7, 9]
[2, 5, 8]
[3, 3, 6, 10]
[0, 11, 12]

Descending runs with equal elements

Our count_run follows the classic rule: a descending run must be strictly decreasing. Python 3.13 relaxed the rule. CPython now accepts equal elements in a descending run, reverses each group of equal elements on the fly, and lets the final reversal restore their original order.

desc_equal.py
import sys


class Num:
    count = 0

    def __init__(self, val):
        self.val = val

    def __lt__(self, other):
        Num.count += 1
        return self.val < other.val


data = [v // 2 for v in range(10_000)][::-1]
print(data[:8])

vals = [Num(v) for v in data]
vals.sort()

print(f'Python {sys.version_info.major}.{sys.version_info.minor}: {Num.count:,} comparisons')

The list is non-increasing, with every value appearing twice. We count the calls to __lt__, the only comparison method the sort uses. In Python 3.12, the input breaks into many short descending runs that must be merged. Since Python 3.13, the whole list is a single run, and the sort ends after a linear number of comparisons.

$ python desc_equal.py
[4999, 4999, 4998, 4998, 4997, 4997, 4996, 4996]
Python 3.15: 14,999 comparisons
$ python3.12 desc_equal.py
[4999, 4999, 4998, 4998, 4997, 4997, 4996, 4996]
Python 3.12: 49,598 comparisons

Computing minrun

On random data, natural runs are short. Timsort extends each run to minrun elements with binary insertion sort. Lists with fewer than 64 elements are sorted by binary insertion sort alone. For longer lists, minrun lies between 32 and 64, chosen so that the number of runs is a power of two or a little less, which keeps the merges balanced.

minrun.py
def minrun_old(n):
    """Python 3.14 and older: one minrun for the whole list."""

    r = 0
    while n >= 64:
        r |= n & 1
        n >>= 1
    return n + r


def minruns_new(n):
    """Python 3.15: run lengths vary by at most one."""

    e = 0
    while (n >> e) >= 64:
        e += 1
    mask = (1 << e) - 1

    current = 0
    total = 0
    while total < n:
        current += n
        size = current >> e
        current &= mask
        total += size
        yield size


for n in (50, 64, 315, 2112, 32769):

    mr = minrun_old(n)
    q, r = divmod(n, mr)
    old = [mr] * q + ([r] if r else [])
    new = list(minruns_new(n))

    print(f'n={n}')
    print(f'  old: minrun {mr}, {len(old)} runs, lengths {sorted(set(old))}')
    print(f'  new: {len(new)} runs, lengths {sorted(set(new))}')

print(list(minruns_new(315)))

The minrun_old function is the rule used up to Python 3.14: it takes the six most significant bits of n and adds one if any of the remaining bits are set. Python 3.15 lets the run length vary by at most one from run to run. The generator keeps a scaled fractional remainder, so the run lengths add up to exactly n, the number of runs is a power of two, and the two runs of every merge differ in length by at most one. For 32769 elements, the old rule produces 993 runs, which is not a power of two, while the new rule produces 1024.

$ python minrun.py
n=50
  old: minrun 50, 1 runs, lengths [50]
  new: 1 runs, lengths [50]
n=64
  old: minrun 32, 2 runs, lengths [32]
  new: 2 runs, lengths [32]
n=315
  old: minrun 40, 8 runs, lengths [35, 40]
  new: 8 runs, lengths [39, 40]
n=2112
  old: minrun 33, 64 runs, lengths [33]
  new: 64 runs, lengths [33]
n=32769
  old: minrun 33, 993 runs, lengths [33]
  new: 1024 runs, lengths [32, 33]
[39, 39, 40, 39, 39, 40, 39, 40]

Binary insertion sort

Insertion sort is fast for short lists, but it does many comparisons. Timsort finds the insertion point with a binary search; the shifting of the elements is a cheap memory move compared to calling __lt__ on Python objects.

binsort.py
from bisect import bisect_right


class Num:
    count = 0

    def __init__(self, val):
        self.val = val

    def __lt__(self, other):
        Num.count += 1
        return self.val < other.val

    def __repr__(self):
        return str(self.val)


def binary_insertion_sort(vals, lo, hi, start):
    """Sort vals[lo:hi]; vals[lo:start] is already sorted."""

    for i in range(start, hi):
        x = vals[i]
        pos = bisect_right(vals, x, lo, i)
        vals[pos + 1:i + 1] = vals[pos:i]
        vals[pos] = x


def linear_insertion_sort(vals, lo, hi, start):

    for i in range(start, hi):
        x = vals[i]
        j = i
        while j > lo and x < vals[j - 1]:
            vals[j] = vals[j - 1]
            j -= 1
        vals[j] = x


data = [3, 8, 12, 5, 1, 9, 14, 2, 7, 11, 4, 13, 6, 10, 0, 15]
print(data)

for sort in (linear_insertion_sort, binary_insertion_sort):
    vals = [Num(v) for v in data]
    Num.count = 0
    sort(vals, 0, len(vals), 3)
    print(f'{sort.__name__:22} {Num.count:3} comparisons  {vals}')

Both functions sort vals[lo:hi] and assume that the first part up to start is already sorted, which is how Timsort calls them after it finds a short natural run. The bisect_right function places an element after equal ones, so the sort stays stable. The Num wrapper counts comparisons. The binary version needs about a third fewer of them for these sixteen numbers.

$ python binsort.py
[3, 8, 12, 5, 1, 9, 14, 2, 7, 11, 4, 13, 6, 10, 0, 15]
linear_insertion_sort   63 comparisons  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
binary_insertion_sort   43 comparisons  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

Merge policy

The runs wait on a stack. Merging them as late as possible could exploit patterns found later, merging them early uses data that is still in the CPU cache. Only adjacent runs may be merged, otherwise equal elements could change their order. Since Python 3.11, CPython uses the powersort policy by Munro and Wild. Each boundary between two runs gets a power: its depth in an ideal balanced merge tree over the whole list.

power.py
def power(s1, n1, n2, n):
    """Depth of the node joining the run s1:s1+n1 with the next run."""

    a = 2 * s1 + n1
    b = a + n1 + n2
    p = 0
    while True:
        p += 1
        if (a << p) // (2 * n) != (b << p) // (2 * n):
            return p


def merge_at(stack, i):
    (s, na, p), (_, nb, _) = stack[i], stack[i + 1]
    print(f'merge {na:3} + {nb:3}')
    stack[i:i + 2] = [(s, na + nb, p)]


def merge_order(lengths):

    n = sum(lengths)
    stack = []
    start = 0

    for n2 in lengths:
        if stack:
            s1, n1, _ = stack[-1]
            p = power(s1, n1, n2, n)
            while len(stack) > 1 and stack[-2][2] > p:
                merge_at(stack, len(stack) - 2)
            stack[-1] = (stack[-1][0], stack[-1][1], p)

        stack.append((start, n2, 0))
        start += n2

    while len(stack) > 1:
        i = len(stack) - 2
        if i > 0 and stack[i - 1][1] < stack[i + 1][1]:
            i -= 1
        merge_at(stack, i)


merge_order([32] * 8)
print()
merge_order([200, 10, 10, 10, 300, 20, 40])

The power function takes the midpoints of the two runs as fractions of the list length and returns the first binary digit in which they differ. When a new run arrives, runs on the stack are merged while the power below the top run is greater than the power of the new boundary. The powers on the stack are therefore strictly decreasing. At the end, the remaining runs are merged from the top, preferring the smaller neighbour. The function only prints the merges. Eight equal runs give a perfectly balanced tree; with uneven runs, the short runs are merged first and the long ones wait.

$ python power.py
merge  32 +  32
merge  32 +  32
merge  64 +  64
merge  32 +  32
merge  32 +  32
merge  64 +  64
merge 128 + 128

merge  10 +  10
merge  20 +  10
merge 200 +  30
merge  20 +  40
merge 300 +  60
merge 230 + 360

Galloping

When a merge takes many elements in a row from the same run, the data is probably clustered. After seven consecutive wins, CPython switches to galloping: it searches the other run for the insertion point with an exponential search. It compares the element with positions 0, 1, 3, 7, 15, and so on, then finishes with a binary search.

gallop.py
class Num:
    count = 0

    def __init__(self, val):
        self.val = val

    def __lt__(self, other):
        Num.count += 1
        return self.val < other.val


def linear_search(vals, x):
    i = 0
    while i < len(vals) and vals[i] < x:
        i += 1
    return i


def gallop(vals, x):
    """Find the position of x in sorted vals, searching from the left."""

    if not vals or not vals[0] < x:
        return 0

    lo, hi = 0, 1
    while hi < len(vals) and vals[hi] < x:
        lo = hi
        hi = 2 * hi + 1
    hi = min(hi, len(vals))

    lo += 1
    while lo < hi:
        mid = (lo + hi) // 2
        if vals[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo


vals = [Num(v) for v in range(0, 2000, 2)]

print(' pos  linear  gallop')
for pos in (0, 1, 2, 4, 6, 10, 50, 500, 999):
    x = Num(2 * pos - 1)

    Num.count = 0
    i = linear_search(vals, x)
    lin = Num.count

    Num.count = 0
    j = gallop(vals, x)
    gal = Num.count

    assert i == j == pos
    print(f'{pos:4} {lin:7} {gal:7}')

We search a sorted list of 1000 even numbers for the position of an odd number. A linear scan needs pos + 1 comparisons. Galloping loses at positions 2 and 4, ties up to position 6, and wins from then on: it needs about 2 log2(pos) comparisons. This is why CPython does not gallop from the start, and it adjusts the threshold during a sort depending on whether galloping pays off.

$ python gallop.py
 pos  linear  gallop
   0       1       1
   1       2       2
   2       3       4
   4       5       6
   6       7       6
  10      11       8
  50      51      12
 500     501      18
 999    1000      19

Timsort implementation

We put the pieces together. Our version has natural runs, the Python 3.15 minrun, binary insertion sort, and the powersort policy. It leaves out galloping; the merge only skips elements that are already in place.

timsort.py
import random
from bisect import bisect_left, bisect_right


def count_run(vals, lo, hi):

    end = lo + 1
    if end == hi:
        return end

    if vals[end] < vals[lo]:
        while end < hi and vals[end] < vals[end - 1]:
            end += 1
        vals[lo:end] = reversed(vals[lo:end])
    else:
        while end < hi and not vals[end] < vals[end - 1]:
            end += 1

    return end


def binary_insertion_sort(vals, lo, hi, start):

    for i in range(start, hi):
        x = vals[i]
        pos = bisect_right(vals, x, lo, i)
        vals[pos + 1:i + 1] = vals[pos:i]
        vals[pos] = x


def minruns(n):

    e = 0
    while (n >> e) >= 64:
        e += 1
    mask = (1 << e) - 1
    current = 0
    while True:
        current += n
        yield current >> e
        current &= mask


def power(s1, n1, n2, n):

    a = 2 * s1 + n1
    b = a + n1 + n2
    p = 0
    while True:
        p += 1
        if (a << p) // (2 * n) != (b << p) // (2 * n):
            return p


def merge(vals, lo, mid, hi):
    """Merge the sorted runs vals[lo:mid] and vals[mid:hi]."""

    # elements already in place need no merging
    lo = bisect_right(vals, vals[mid], lo, mid)
    hi = bisect_left(vals, vals[mid - 1], mid, hi)
    if lo == mid or mid == hi:
        return

    left = vals[lo:mid]
    i, j, k = 0, mid, lo
    while i < len(left) and j < hi:
        if vals[j] < left[i]:
            vals[k] = vals[j]
            j += 1
        else:
            vals[k] = left[i]
            i += 1
        k += 1
    vals[k:k + len(left) - i] = left[i:]


def timsort(vals):

    n = len(vals)
    if n < 2:
        return

    sizes = minruns(n)
    stack = []
    lo = 0

    while lo < n:
        minrun = next(sizes)
        end = count_run(vals, lo, n)
        if end - lo < minrun:
            force = min(lo + minrun, n)
            binary_insertion_sort(vals, lo, force, end)
            end = force

        if stack:
            s1, n1, _ = stack[-1]
            p = power(s1, n1, end - lo, n)
            while len(stack) > 1 and stack[-2][2] > p:
                (sa, na, pa), (sb, nb, _) = stack[-2:]
                merge(vals, sa, sb, sb + nb)
                stack[-2:] = [(sa, na + nb, pa)]
            stack[-1] = (*stack[-1][:2], p)

        stack.append((lo, end - lo, 0))
        lo = end

    while len(stack) > 1:
        (sa, na, pa), (sb, nb, _) = stack[-2:]
        merge(vals, sa, sb, sb + nb)
        stack[-2:] = [(sa, na + nb, pa)]


class Item:

    def __init__(self, key, pos):
        self.key = key
        self.pos = pos

    def __lt__(self, other):
        return self.key < other.key


random.seed(5)
vals = [random.randint(0, 99) for _ in range(20)]
print(vals)
timsort(vals)
print(vals)

for n in range(1000):
    items = [Item(random.randint(0, n // 4), i) for i in range(n)]
    timsort(items)
    assert [(it.key, it.pos) for it in items] == sorted((it.key, it.pos) for it in items)

print('1000 lists sorted correctly and stably')

Before merging, merge uses bisect_right to find the elements of the left run that are smaller than the first element of the right run, and bisect_left to find the elements of the right run that are greater than the last element of the left run. These are already in their final places. Only the rest of the left run is copied to a temporary list, so the extra memory is at most half the list. On ties, the element from the left run wins, which keeps the sort stable. The test sorts Item objects with many equal keys and checks that items with equal keys keep their original order.

$ python timsort.py
[79, 32, 94, 45, 88, 94, 83, 67, 3, 59, 99, 31, 83, 6, 20, 14, 47, 60, 31, 48]
[3, 6, 14, 20, 31, 31, 32, 45, 47, 48, 59, 60, 67, 79, 83, 83, 88, 94, 94, 99]
1000 lists sorted correctly and stably

Counting comparisons

No comparison sort can sort random input with fewer than log2(n!) comparisons on average. We count how many comparisons the built-in sort makes for 10,000 elements of different shapes.

comparisons.py
import math
import random


class Num:
    count = 0

    def __init__(self, val):
        self.val = val

    def __lt__(self, other):
        Num.count += 1
        return self.val < other.val


def count(data):
    vals = [Num(v) for v in data]
    Num.count = 0
    vals.sort()
    return Num.count


random.seed(1)
n = 10_000
asc = list(range(n))

inputs = {
    'random': random.sample(asc, n),
    'sorted': asc,
    'reversed': asc[::-1],
    'sorted + 10 random': asc + random.sample(range(n), 10),
    'four sorted runs': [v for k in range(4) for v in asc[k::4]],
    'ten unique values': [random.randrange(10) for _ in range(n)],
}

bound = math.lgamma(n + 1) / math.log(2)
print(f'lg(n!) for random input: {bound:,.0f}')
print(f'n log2 n:                {n * math.log2(n):,.0f}')
print()

for name, data in inputs.items():
    print(f'{name:20} {count(data):8,}')

On random input, the sort is within about 1.4% of the theoretical lower bound. Sorted and reversed lists are single runs, so they need exactly n - 1 comparisons. A sorted list with ten random numbers appended is barely more expensive. Four interleaved sorted sequences become four natural runs. With only ten distinct values, merges meet long stretches of equal elements, and galloping skips over them.

$ python comparisons.py
lg(n!) for random input: 118,458
n log2 n:                132,877

random                120,100
sorted                  9,999
reversed                9,999
sorted + 10 random     10,242
four sorted runs       30,001
ten unique values      71,236

Key functions

With the key parameter, the sort computes each key once and then sorts the keys, carrying the elements along.

key_calls.py
calls = 0


def key(word):
    global calls
    calls += 1
    return len(word)


words = ['sky', 'blue', 'cup', 'forest', 'top', 'water', 'ocean', 'up', 'a']

result = sorted(words, key=key)

print(result)
print(f'{len(words)} words, {calls} key calls')

The key function is called once per element, no matter how many comparisons the sort makes. Words of the same length keep their original order: sky, cup, top.

$ python key_calls.py
['a', 'up', 'sky', 'cup', 'top', 'blue', 'water', 'ocean', 'forest']
9 words, 9 key calls

Stability and reverse

Stability also holds for the reverse=True parameter. It is not the same as reversing the sorted result.

stable.py
from operator import itemgetter

grades = [
    ('Anna', 'B'), ('Peter', 'A'), ('Lucia', 'C'), ('Martin', 'A'),
    ('Eva', 'B'), ('Jozef', 'C'), ('Zuzana', 'A'),
]

print(sorted(grades, key=itemgetter(1)))
print(sorted(grades, key=itemgetter(1), reverse=True))
print(sorted(grades, key=itemgetter(1))[::-1])

With reverse=True, the grades are in descending order, but students with the same grade keep their original order: Peter, Martin, Zuzana. Reversing the result of an ascending sort reverses the equal elements too. Internally, the sort reverses the list, sorts it stably, and reverses it back.

$ python stable.py
[('Peter', 'A'), ('Martin', 'A'), ('Zuzana', 'A'), ('Anna', 'B'), ('Eva', 'B'), ('Lucia', 'C'), ('Jozef', 'C')]
[('Lucia', 'C'), ('Jozef', 'C'), ('Anna', 'B'), ('Eva', 'B'), ('Peter', 'A'), ('Martin', 'A'), ('Zuzana', 'A')]
[('Jozef', 'C'), ('Lucia', 'C'), ('Eva', 'B'), ('Anna', 'B'), ('Zuzana', 'A'), ('Martin', 'A'), ('Peter', 'A')]

Type-specialized comparisons

Since Python 3.7, the sort first checks whether all elements have the same type. For lists of small integers, floats, strings, or tuples whose first elements share a type, it replaces the generic comparison with a faster specialized one.

homogeneous.py
import random
import timeit

random.seed(2)
n = 200_000

ints = [random.randrange(10**9) for _ in range(n)]
floats = [float(v) for v in ints]
mixed = ints[:-1] + [float(ints[-1])]
strs = [str(v) for v in ints]
tuples = [(v, v) for v in ints]

for name, data in [('ints', ints), ('floats', floats),
                   ('ints + one float', mixed), ('strings', strs),
                   ('tuples', tuples)]:
    t = min(timeit.repeat(lambda: sorted(data), number=5, repeat=5)) / 5
    print(f'{name:18} {t * 1000:6.1f} ms')

We sort 200,000 numbers in several forms. Replacing the last integer with a float makes the list mixed, and the sort falls back to the generic comparison; it gets much slower although it sorts the same values. Tuples are the slowest: each comparison first looks for the first pair of items that differ, and only then compares them. The times vary between runs and machines.

$ python homogeneous.py
ints                 31.9 ms
floats               29.9 ms
ints + one float     52.6 ms
strings              52.8 ms
tuples               99.5 ms

Benchmark

Finally, we time the built-in sort on one million integers of different shapes.

benchmark.py
import random
import timeit

random.seed(3)
n = 1_000_000
asc = list(range(n))

inputs = {
    'random': random.sample(asc, n),
    'sorted': asc,
    'reversed': asc[::-1],
    'sorted + 1000 random': asc + random.sample(range(n), 1000),
    'ten unique values': [random.randrange(10) for _ in range(n)],
}

for name, data in inputs.items():
    t = min(timeit.repeat(lambda: sorted(data), number=1, repeat=5))
    print(f'{name:22} {t * 1000:7.1f} ms')

A sorted or reversed list is sorted almost 30 times faster than a random one, and appending a thousand random numbers to a sorted list barely changes that. This adaptivity is the main reason for Timsort's design: real data is often partially ordered. The times vary between runs and machines.

$ python benchmark.py
random                   310.4 ms
sorted                    10.9 ms
reversed                  12.2 ms
sorted + 1000 random      12.9 ms
ten unique values         62.4 ms

Source

listsort.txt – Timsort description in the CPython repository

Sorting Techniques – Python documentation

Nearly-Optimal Mergesorts – Munro and Wild

In this article we have explained Timsort, the algorithm behind list.sort and sorted, and implemented it in Python. See also Python merge sort, Python insertion sort, Python sort list, and Python sorted function.

Author

I am Jan Bodnar, a programmer and technical writer. I have been writing programming tutorials at ZetCode since 2007 and have published eight e-books. See about the author.

List all Python tutorials.