Python introsort
last modified November 18, 2026 Python 3.15
In this article we implement introsort in Python. Introsort, short for introspective sort, is a quick sort that watches its own recursion depth. When the depth gets too large, it switches to heap sort, and it finishes small slices with insertion sort.
Quick sort is fast on average, but bad
pivots make it quadratic. Heap sort is
always O(n log n), but slower in practice.
Insertion sort is quadratic, but the
fastest for a handful of elements. Introsort, published by David Musser in
1997, combines the strengths of all three. It is the algorithm behind
std::sort in the GCC C++ standard library and
Array.Sort in .NET.
Introsort algorithm
Introsort starts as a quick sort with a depth budget of
2 * floor(log2(n)). Every partition uses one level of the
budget. A slice that runs out of budget is sorted with heap sort. A slice
with at most 16 elements is left to insertion sort.
| Property | Value |
|---|---|
| Time (average and worst) | O(n log n) |
| Extra space | O(log n) for the recursion |
| Stable | no |
| In place | yes |
Python does not use introsort; list.sort and
sorted use the stable Timsort.
Introsort is the typical choice when the sort may be unstable and must not
allocate memory.
Introsort example
The following module implements introsort. The other examples in this article import it.
import random
THRESHOLD = 16
def insertion_sort(vals, lo, hi):
for i in range(lo + 1, hi):
x = vals[i]
j = i
while j > lo and x < vals[j - 1]:
vals[j] = vals[j - 1]
j -= 1
vals[j] = x
def sift_down(vals, lo, root, size):
while True:
child = 2 * root + 1
if child >= size:
return
if child + 1 < size and vals[lo + child] < vals[lo + child + 1]:
child += 1
if not vals[lo + root] < vals[lo + child]:
return
vals[lo + root], vals[lo + child] = vals[lo + child], vals[lo + root]
root = child
def heap_sort(vals, lo, hi):
size = hi - lo
for root in range(size // 2 - 1, -1, -1):
sift_down(vals, lo, root, size)
for end in range(size - 1, 0, -1):
vals[lo], vals[lo + end] = vals[lo + end], vals[lo]
sift_down(vals, lo, 0, end)
def median_of_three(vals, a, b, c):
if vals[a] < vals[b]:
if vals[b] < vals[c]:
return b
return c if vals[a] < vals[c] else a
if vals[a] < vals[c]:
return a
return c if vals[b] < vals[c] else b
def partition(vals, lo, hi):
"""Hoare partition around the median of three; returns the split point."""
mid = (lo + hi - 1) // 2
m = median_of_three(vals, lo, mid, hi - 1)
pivot = vals[m]
i, j = lo - 1, hi
while True:
i += 1
while vals[i] < pivot:
i += 1
j -= 1
while pivot < vals[j]:
j -= 1
if i >= j:
return j + 1
vals[i], vals[j] = vals[j], vals[i]
def intro_loop(vals, lo, hi, depth):
while hi - lo > THRESHOLD:
if depth == 0:
heap_sort(vals, lo, hi)
return
depth -= 1
p = partition(vals, lo, hi)
# recurse into the smaller part, loop on the larger one
if p - lo < hi - p:
intro_loop(vals, lo, p, depth)
lo = p
else:
intro_loop(vals, p, hi, depth)
hi = p
insertion_sort(vals, lo, hi)
def introsort(vals, limit=True):
"""Sort vals in place; with limit=False it is a plain quick sort."""
n = len(vals)
depth = 2 * (n.bit_length() - 1) if limit else n
intro_loop(vals, 0, n, depth)
if __name__ == '__main__':
random.seed(4)
vals = [random.randint(0, 99) for _ in range(30)]
print(vals)
introsort(vals)
print(vals)
for n in range(500):
data = [random.randint(0, n // 2 + 1) for _ in range(n)]
vals = data[:]
introsort(vals)
assert vals == sorted(data)
print('500 random lists sorted correctly')
The partition function picks the median of the first, middle,
and last element as the pivot and uses Hoare's partition scheme. It returns
a split point p: all elements in vals[lo:p] are
less than or equal to the pivot, all in vals[p:hi] are greater
than or equal to it. The intro_loop function recurses into the
smaller part and loops on the larger one, so the recursion is never deeper
than log2(n), even when the depth budget would allow more. When
depth reaches zero, the slice goes to heap_sort,
which sorts vals[lo:hi] in place by offsetting all heap
indexes by lo. With limit=False, the budget is so
large that it never runs out, and the function is a plain quick sort; we use
it for comparison.
$ python introsort.py [30, 38, 13, 92, 50, 61, 19, 11, 8, 2, 51, 70, 37, 97, 7, 28, 66, 68, 46, 35, 99, 22, 13, 33, 27, 3, 82, 33, 34, 24] [2, 3, 7, 8, 11, 13, 13, 19, 22, 24, 27, 28, 30, 33, 33, 34, 35, 37, 38, 46, 50, 51, 61, 66, 68, 70, 82, 92, 97, 99] 500 random lists sorted correctly
A killer adversary
Median-of-three pivots handle sorted and reversed input well, so where does the worst case come from? In 1999, Douglas McIlroy described an adversary that builds a bad input for any quick sort. It does not know the values in advance. It decides them during the sort, always in the way that makes the current pivot as bad as possible.
from introsort import introsort
def make_killer(n, sort):
"""McIlroy's adversary: decide values lazily to make sort slow."""
gas = n
val = [gas] * n
solid = 0
candidate = 0
def freeze(i):
nonlocal solid
val[i] = solid
solid += 1
class Lazy:
def __init__(self, idx):
self.idx = idx
def __lt__(self, other):
nonlocal candidate
x, y = self.idx, other.idx
if val[x] == gas and val[y] == gas:
freeze(x if x == candidate else y)
if val[x] == gas:
candidate = x
elif val[y] == gas:
candidate = y
return val[x] < val[y]
sort([Lazy(i) for i in range(n)])
return val
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, sort):
vals = [Num(v) for v in data]
Num.count = 0
sort(vals)
assert [v.val for v in vals] == sorted(data)
return Num.count
def quick_sort(vals):
introsort(vals, limit=False)
if __name__ == '__main__':
killer = make_killer(40, quick_sort)
print(killer)
print()
print(' n quick sort introsort')
for n in (1000, 2000, 4000, 8000):
data = make_killer(n, quick_sort)
print(f'{n:6} {count(data, quick_sort):12,} {count(data, introsort):12,}')
All elements start as gas
, a value larger than everything else. When
two gas elements are compared, one of them is frozen to the next smallest
value. The adversary remembers the gas element of the latest comparison as
the probable pivot. When it meets another gas element, the other one is
frozen, so the pivot stays gas and ends up larger than nearly everything in
its slice. The Lazy objects record the frozen values in
val, and the result is an ordinary list of numbers. The sort is
deterministic, so it makes the same comparisons when it sorts this list
again. For the quick sort, the number of comparisons grows four times when
n doubles, which is quadratic growth. Introsort handles the same
input in O(n log n).
$ python killer.py
[0, 28, 2, 20, 4, 29, 6, 22, 8, 30, 10, 24, 12, 25, 14, 26, 16, 27, 18, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 31, 32, 33, 34, 35, 36, 37, 38, 40]
n quick sort introsort
1000 252,903 33,488
2000 1,005,903 75,680
4000 4,011,903 168,003
8000 16,023,903 369,143
Tracing the fallback
We replace heap_sort in the introsort module with a
function that reports where the fallback happens.
import introsort
from killer import make_killer, quick_sort
original = introsort.heap_sort
def traced_heap_sort(vals, lo, hi):
print(f'heap sort fallback on vals[{lo}:{hi}]')
original(vals, lo, hi)
introsort.heap_sort = traced_heap_sort
data = make_killer(2000, quick_sort)
print('depth limit:', 2 * (len(data).bit_length() - 1))
introsort.introsort(data)
print('sorted:', data == sorted(data))
The intro_loop function looks up heap_sort in its
module globals at call time, so assigning to
introsort.heap_sort replaces it for the next sort. On the killer
input, each partition splits off only two elements. After 20 partitions, the
budget is spent, and heap sort takes over the remaining 1960 elements.
$ python trace.py depth limit: 20 heap sort fallback on vals[40:2000] sorted: True
Counting comparisons
We count the comparisons of quick sort, heap sort, introsort, and the
built-in list.sort on 10,000 elements of different shapes.
import random
from introsort import introsort, heap_sort
from killer import make_killer, count, quick_sort
random.seed(6)
n = 10_000
asc = list(range(n))
inputs = {
'random': random.sample(asc, n),
'sorted': asc,
'reversed': asc[::-1],
'ten unique values': [random.randrange(10) for _ in range(n)],
'all equal': [7] * n,
'quick sort killer': make_killer(n, quick_sort),
}
sorts = {
'quick sort': quick_sort,
'heap sort': lambda vals: heap_sort(vals, 0, len(vals)),
'introsort': introsort,
'sorted': lambda vals: vals.sort(),
}
print(f'{"":18}' + ''.join(f'{name:>12}' for name in sorts))
for name, data in inputs.items():
counts = [count(data, sort) for sort in sorts.values()]
print(f'{name:18}' + ''.join(f'{c:12,}' for c in counts))
On ordinary input, introsort never reaches the depth limit and makes exactly the same comparisons as quick sort. Heap sort makes about 40% more, and it gains nothing from sorted data. On the killer input, quick sort needs 25 million comparisons; introsort pays for its 26 wasted partitions and then for heap sort, but stays below half a million. The killer was built against our quick sort, so the built-in Timsort is not hurt by it; it even finds long runs in it. Introsort is not adaptive: it needs over 100,000 comparisons for sorted input, where Timsort needs 9,999.
$ python compare.py
quick sort heap sort introsort sorted
random 164,566 235,216 164,566 120,121
sorted 112,045 244,460 112,045 9,999
reversed 112,047 226,682 112,047 9,999
ten unique values 115,977 217,901 115,977 71,185
all equal 113,547 29,994 113,547 9,999
quick sort killer 25,029,903 231,638 489,847 44,497
Insertion sort threshold
The threshold below which slices go to insertion sort is a tuning parameter. We time the sort of 100,000 floats with different thresholds.
import random
import timeit
import introsort
random.seed(7)
data = [random.random() for _ in range(100_000)]
for threshold in (1, 4, 8, 16, 32, 64, 128):
introsort.THRESHOLD = threshold
t = min(timeit.repeat(lambda: introsort.introsort(data[:]),
number=1, repeat=3))
print(f'threshold {threshold:3}: {t * 1000:6.0f} ms')
Since intro_loop reads THRESHOLD from the module
globals, we can change it from outside. A threshold of 1 means pure quick
sort with heap sort fallback, and it is slower: partitioning tiny slices
costs more than the insertion sort it replaces. Large thresholds make the
quadratic insertion sort dominate. Between 8 and 32, the times are close.
C++ libraries use 16. The times vary between runs and machines.
$ python threshold.py threshold 1: 118 ms threshold 4: 90 ms threshold 8: 86 ms threshold 16: 84 ms threshold 32: 91 ms threshold 64: 115 ms threshold 128: 166 ms
Benchmark
Finally, we time the sorts on 20,000 random numbers and on a killer input of the same size.
import random
import timeit
from introsort import introsort, heap_sort
from killer import make_killer, quick_sort
random.seed(8)
n = 20_000
data = random.sample(range(n), n)
killer = make_killer(n, quick_sort)
tests = [
('quick sort', quick_sort),
('heap sort', lambda vals: heap_sort(vals, 0, len(vals))),
('introsort', introsort),
('sorted', sorted),
]
print(f'{"":12} {"random":>10} {"killer":>10}')
for name, sort in tests:
t1 = min(timeit.repeat(lambda: sort(data[:]), number=1, repeat=3))
t2 = min(timeit.repeat(lambda: sort(killer[:]), number=1, repeat=3))
print(f'{name:12} {t1 * 1000:8.1f} ms {t2 * 1000:7.1f} ms')
On random data, introsort runs as fast as quick sort and about three times
faster than heap sort. On the killer input, quick sort takes seconds, while
introsort stays in the same range as heap sort. The built-in
sorted, written in C, beats all of them. The times vary between
runs and machines.
$ python benchmark.py
random killer
quick sort 13.1 ms 2156.2 ms
heap sort 39.7 ms 36.5 ms
introsort 13.0 ms 49.4 ms
sorted 2.6 ms 0.5 ms
Source
Introspective Sorting and Selection Algorithms – David R. Musser
A Killer Adversary for Quicksort – M. D. McIlroy
Sorting Techniques – Python documentation
In this article we have implemented introsort in Python and shown how its depth limit protects quick sort from the quadratic worst case. See also Python quick sort, Python heap sort, Python insertion sort, and Python Timsort.
Author
List all Python tutorials.