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.
| Property | Value |
|---|---|
| Time, best case (sorted or reversed input) | O(n) |
| Time, average and worst case | O(n log n) |
| Extra space | O(n), at most n/2 references for a merge |
| Stable | yes |
| Adaptive | yes, 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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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
List all Python tutorials.