ZetCode

Python sorting algorithms compared

last modified November 18, 2026 Python 3.15

In this article we compare classic sorting algorithms side by side. We summarize their properties, test their stability, count their comparisons, and time them on the same data. Each algorithm has its own article with a detailed explanation; this page shows how they relate.

Overview

The table lists the time and space complexity of each algorithm, where n is the number of elements, k the range of values, d the number of digits, and b the base. An algorithm is stable when equal elements keep their original order, and adaptive when it runs faster on partially sorted input.

AlgorithmBestAverageWorstExtra spaceStableAdaptive
Bubble sortO(n)O(n2)O(n2)O(1)yesyes
Selection sortO(n2)O(n2)O(n2)O(1)nono
Insertion sortO(n)O(n2)O(n2)O(1)yesyes
Shell sortO(n log n)depends on gapsbelow O(n2) with good gapsO(1)noyes
Merge sortO(n log n)O(n log n)O(n log n)O(n)yesno
Quick sortO(n log n)O(n log n)O(n2)O(log n)nono
Heap sortO(n log n)O(n log n)O(n log n)O(1)nono
IntrosortO(n log n)O(n log n)O(n log n)O(log n)nono
TimsortO(n)O(n log n)O(n log n)O(n)yesyes
Counting sortO(n + k)O(n + k)O(n + k)O(n + k)yesno
Radix sortO(d(n + b))O(d(n + b))O(d(n + b))O(n + b)yesno
Bucket sortO(n)O(n) for uniform dataO(n2)O(n)yesno

The first nine algorithms are comparison sorts: they learn about the order only by comparing two elements. No comparison sort can do better than O(n log n) comparisons on average. Counting, radix, and bucket sort get around this limit by using the values themselves, so they only work for integers, fixed-length keys, or numbers from a known range.

The implementations

To compare the algorithms on equal terms, we collect compact versions of them in one module. The following examples import it.

sorts.py
"""Compact versions of classic sorting algorithms.

Every function returns a new sorted list and compares elements only
with <, so they work with any objects that define __lt__.
"""

import heapq


def bubble_sort(vals):
    vals = list(vals)
    for end in range(len(vals) - 1, 0, -1):
        swapped = False
        for i in range(end):
            if vals[i + 1] < vals[i]:
                vals[i], vals[i + 1] = vals[i + 1], vals[i]
                swapped = True
        if not swapped:
            break
    return vals


def selection_sort(vals):
    vals = list(vals)
    for i in range(len(vals) - 1):
        m = i
        for j in range(i + 1, len(vals)):
            if vals[j] < vals[m]:
                m = j
        vals[i], vals[m] = vals[m], vals[i]
    return vals


def insertion_sort(vals):
    vals = list(vals)
    for i in range(1, len(vals)):
        x = vals[i]
        j = i
        while j > 0 and x < vals[j - 1]:
            vals[j] = vals[j - 1]
            j -= 1
        vals[j] = x
    return vals


def shell_sort(vals):
    vals = list(vals)
    gaps = [701, 301, 132, 57, 23, 10, 4, 1]
    while gaps[0] * 2.25 < len(vals):
        gaps.insert(0, int(gaps[0] * 2.25))
    for gap in gaps:
        for i in range(gap, len(vals)):
            x = vals[i]
            j = i
            while j >= gap and x < vals[j - gap]:
                vals[j] = vals[j - gap]
                j -= gap
            vals[j] = x
    return vals


def merge_sort(vals):
    if len(vals) <= 1:
        return list(vals)
    mid = len(vals) // 2
    left, right = merge_sort(vals[:mid]), merge_sort(vals[mid:])
    res = []
    i = j = 0
    while i < len(left) and j < len(right):
        if right[j] < left[i]:
            res.append(right[j])
            j += 1
        else:
            res.append(left[i])
            i += 1
    res.extend(left[i:])
    res.extend(right[j:])
    return res


def quick_sort(vals):
    vals = list(vals)
    stack = [(0, len(vals) - 1)]
    while stack:
        lo, hi = stack.pop()
        if lo >= hi:
            continue
        mid = (lo + hi) // 2
        vals[mid], vals[hi] = vals[hi], vals[mid]
        pivot = vals[hi]
        i = lo
        for j in range(lo, hi):
            if vals[j] < pivot:
                vals[i], vals[j] = vals[j], vals[i]
                i += 1
        vals[i], vals[hi] = vals[hi], vals[i]
        stack += [(lo, i - 1), (i + 1, hi)]
    return vals


def heap_sort(vals):
    heap = list(vals)
    heapq.heapify(heap)
    return [heapq.heappop(heap) for _ in range(len(heap))]


def counting_sort(vals):
    """Non-negative integers only."""
    counts = [0] * (max(vals, default=0) + 1)
    for v in vals:
        counts[v] += 1
    return [v for v, c in enumerate(counts) for _ in range(c)]


def radix_sort(vals):
    """Non-negative integers only, base 256."""
    vals = list(vals)
    shift = 0
    while vals and max(vals) >> shift:
        buckets = [[] for _ in range(256)]
        for v in vals:
            buckets[(v >> shift) & 255].append(v)
        vals = [v for b in buckets for v in b]
        shift += 8
    return vals


def bucket_sort(vals):
    """Floats in [0, 1) only."""
    buckets = [[] for _ in range(len(vals))]
    for v in vals:
        buckets[int(v * len(vals))].append(v)
    return [v for b in buckets for v in insertion_sort(b)]


COMPARISON_SORTS = {
    'bubble': bubble_sort,
    'selection': selection_sort,
    'insertion': insertion_sort,
    'shell': shell_sort,
    'merge': merge_sort,
    'quick': quick_sort,
    'heap': heap_sort,
    'sorted': sorted,
}

Every function returns a new list and compares elements only with <. Bubble sort stops early when a pass makes no swaps. Shell sort uses the Ciura gap sequence, extended by a factor of 2.25 for long lists. Quick sort is the Lomuto scheme with the middle element as the pivot and an explicit stack instead of recursion. Heap sort uses the heapq module, which is written in C, so it is not in place and its timings are not comparable with the pure Python sorts. The last three functions accept only the data they are designed for. The built-in sorted function, a C implementation of Timsort, is included for reference.

Stability

We sort 200 records with only ten different keys and check whether records with equal keys keep their original order.

stability.py
import random

from sorts import COMPARISON_SORTS


class Record:

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

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


random.seed(1)
records = [Record(random.randrange(10), pos) for pos in range(200)]
expected = sorted((r.key, r.pos) for r in records)

for name, sort in COMPARISON_SORTS.items():
    result = [(r.key, r.pos) for r in sort(records)]
    print(f'{name:10} {"stable" if result == expected else "not stable"}')

The Record class compares only by key; the pos attribute remembers the original position. A stable sort returns the records ordered by key and, within a key, by position, which is exactly the order of the sorted (key, pos) tuples. Algorithms that swap elements over long distances, such as selection, shell, quick, and heap sort, lose the original order of equal elements.

$ python stability.py
bubble     stable
selection  not stable
insertion  stable
shell      not stable
merge      stable
quick      not stable
heap       not stable
sorted     stable

Counting comparisons

Comparisons are the main cost of sorting Python objects, because each one calls __lt__. We count them for 1000 elements in four arrangements. The nearly sorted list is a sorted list with ten random swaps.

comparisons.py
import random

from sorts import COMPARISON_SORTS


class Num:
    count = 0

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

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


random.seed(2)
n = 1000
asc = list(range(n))
nearly = asc[:]
for _ in range(10):
    i, j = random.randrange(n), random.randrange(n)
    nearly[i], nearly[j] = nearly[j], nearly[i]

inputs = {
    'random': random.sample(asc, n),
    'sorted': asc,
    'reversed': asc[::-1],
    'nearly sorted': nearly,
}

print(f'{"":10}' + ''.join(f'{name:>15}' for name in inputs))
for name, sort in COMPARISON_SORTS.items():
    row = []
    for data in inputs.values():
        Num.count = 0
        sort([Num(v) for v in data])
        row.append(Num.count)
    print(f'{name:10}' + ''.join(f'{c:15,}' for c in row))

Selection sort always makes n(n - 1) / 2 comparisons, whatever the input. Bubble sort and insertion sort need only n - 1 for sorted input, but insertion sort profits from nearly sorted data much more: a single small element near the end needs a whole bubble sort pass per position to move to the front. Merge, quick, and heap sort stay near n log2 n, about 10,000. The built-in sort matches merge sort on random data and handles sorted, reversed, and nearly sorted input in a fraction of that.

$ python comparisons.py
                   random         sorted       reversed  nearly sorted
bubble            498,419            999        499,500        449,414
selection         499,500        499,500        499,500        499,500
insertion         259,999            999        499,500          5,989
shell              13,051          6,771          9,354          8,809
merge               8,664          4,932          5,044          6,415
quick              10,514          7,987          8,406          8,437
heap               10,294         10,769         10,379         10,744
sorted              8,665            999            999          2,586

Growth

Complexity classes describe how the running time grows with the input. We double n three times and time insertion sort and merge sort.

growth.py
import random
import timeit

from sorts import insertion_sort, merge_sort

random.seed(3)

print(f'{"n":>6} {"insertion":>12} {"merge":>12}')
for n in (1000, 2000, 4000, 8000):
    data = [random.random() for _ in range(n)]
    t1 = min(timeit.repeat(lambda: insertion_sort(data), number=1, repeat=3))
    t2 = min(timeit.repeat(lambda: merge_sort(data), number=1, repeat=3))
    print(f'{n:6} {t1 * 1000:9.1f} ms {t2 * 1000:9.1f} ms')

Each doubling makes insertion sort about four times slower, as expected for O(n2), while merge sort takes a little more than twice as long, as expected for O(n log n). At 8000 elements, merge sort is about eighty times faster. The times vary between runs and machines.

$ python growth.py
     n    insertion        merge
  1000       9.5 ms       0.9 ms
  2000      41.4 ms       1.9 ms
  4000     182.9 ms       4.3 ms
  8000     755.7 ms       8.9 ms

Small inputs

For small lists, the constant factors matter more than the complexity class. We time the sorts on lists of 4 to 128 floats.

small.py
import random
import timeit

from sorts import insertion_sort, merge_sort, quick_sort

random.seed(4)

print(f'{"n":>4} {"insertion":>11} {"merge":>9} {"quick":>9}')
for n in (4, 8, 16, 32, 64, 128):
    data = [random.random() for _ in range(n)]
    row = []
    for sort in (insertion_sort, merge_sort, quick_sort):
        t = min(timeit.repeat(lambda: sort(data), number=2000, repeat=5))
        row.append(t / 2000 * 1e6)
    print(f'{n:4} {row[0]:8.1f} µs {row[1]:6.1f} µs {row[2]:6.1f} µs')

Insertion sort is the fastest up to about 16 elements, despite its quadratic complexity, because it has no recursion and no extra lists. This is why practical sorts such as Timsort and introsort use insertion sort for short runs and small slices. The times vary between runs and machines.

$ python small.py
   n   insertion     merge     quick
   4      0.4 µs    1.3 µs    1.1 µs
   8      1.0 µs    3.2 µs    1.8 µs
  16      2.9 µs    7.7 µs    3.9 µs
  32     13.6 µs   18.5 µs   10.4 µs
  64     47.2 µs   40.2 µs   22.4 µs
 128    174.9 µs   91.2 µs   47.2 µs

Benchmark

Finally, we time all algorithms on 5000 random integers, and bucket sort on 5000 random floats.

benchmark.py
import random
import timeit

import sorts

random.seed(5)
n = 5000
ints = [random.randrange(n) for _ in range(n)]
floats = [random.random() for _ in range(n)]

tests = [(name, sort, ints) for name, sort in sorts.COMPARISON_SORTS.items()]
tests += [
    ('counting', sorts.counting_sort, ints),
    ('radix', sorts.radix_sort, ints),
    ('bucket', sorts.bucket_sort, floats),
]

for name, sort, data in tests:
    t = min(timeit.repeat(lambda: sort(data), number=1, repeat=3))
    print(f'{name:10} {t * 1000:8.2f} ms')

The three quadratic sorts take hundreds of milliseconds; bubble sort is the slowest because it swaps elements one position at a time. The O(n log n) sorts in pure Python take a few milliseconds. Heap sort is fast only because the heap operations run in C. Counting sort, written in Python, is about as fast as the built-in sorted here, because the values come from a small range. For general data, the built-in sort is the right choice. The times vary between runs and machines.

$ python benchmark.py
bubble       598.57 ms
selection    272.52 ms
insertion    287.90 ms
shell          4.72 ms
merge          5.78 ms
quick          3.33 ms
heap           0.95 ms
sorted         0.49 ms
counting       0.61 ms
radix          0.88 ms
bucket         1.35 ms

Choosing an algorithm

In Python code, use list.sort or sorted. They are stable, adaptive, written in C, and accept a key function. The other algorithms are worth knowing for the following situations.

Source

Sorting Techniques – Python documentation

list.sort – Python documentation

In this article we have compared sorting algorithms in Python by their complexity, stability, comparison counts, and running times. See the articles on the individual algorithms linked in the overview table, as well as 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.