ZetCode

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.

PropertyValue
Time (average and worst)O(n log n)
Extra spaceO(log n) for the recursion
Stableno
In placeyes

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.

introsort.py
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.

killer.py
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.

trace.py
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.

compare.py
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.

threshold.py
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.

benchmark.py
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

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.