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.
| Algorithm | Best | Average | Worst | Extra space | Stable | Adaptive |
|---|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n2) | O(n2) | O(1) | yes | yes |
| Selection sort | O(n2) | O(n2) | O(n2) | O(1) | no | no |
| Insertion sort | O(n) | O(n2) | O(n2) | O(1) | yes | yes |
| Shell sort | O(n log n) | depends on gaps | below O(n2) with good gaps | O(1) | no | yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | yes | no |
| Quick sort | O(n log n) | O(n log n) | O(n2) | O(log n) | no | no |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | no | no |
| Introsort | O(n log n) | O(n log n) | O(n log n) | O(log n) | no | no |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | yes | yes |
| Counting sort | O(n + k) | O(n + k) | O(n + k) | O(n + k) | yes | no |
| Radix sort | O(d(n + b)) | O(d(n + b)) | O(d(n + b)) | O(n + b) | yes | no |
| Bucket sort | O(n) | O(n) for uniform data | O(n2) | O(n) | yes | no |
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.
"""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.
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.
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.
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.
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.
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.
- Insertion sort for very small or nearly sorted data, also as a building block of other sorts.
- Merge sort when data does not fit in memory, or when merging already
sorted sequences, for example with
heapq.merge. - Heap sort or introsort when the sort must not allocate memory and the worst case must stay O(n log n).
- Counting and radix sort for many integers from a small range or keys of fixed length.
- Bucket sort for numbers spread evenly over a known range.
- Partial sorting with
heapq.nsmallestorheapq.nlargestwhen only the top few elements are needed.
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
List all Python tutorials.