Introsort in Python
Quicksort that switches to heapsort at depth limit and to insertion sort on small ranges; O(n log n) worst case.
- File
introsort.py, 105 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/introsort/. The authors are listed in prov/S172EG.jsonl.
from typing import Protocol, TypeVar
class Ordered(Protocol):
def __lt__(self, other: "Ordered", /) -> bool: ...
T = TypeVar("T", bound=Ordered)
SMALL = 16
def _insertion_sort(a: list[T], lo: int, hi: int) -> None:
for i in range(lo + 1, hi):
x = a[i]
j = i
while j > lo and x < a[j - 1]:
a[j] = a[j - 1]
j -= 1
a[j] = x
def _sift_down(a: list[T], lo: int, i: int, size: int) -> None:
x = a[lo + i]
while True:
c = 2 * i + 1
if c >= size:
break
if c + 1 < size and a[lo + c] < a[lo + c + 1]:
c += 1
if not x < a[lo + c]:
break
a[lo + i] = a[lo + c]
i = c
a[lo + i] = x
def _heapsort(a: list[T], lo: int, hi: int) -> None:
size = hi - lo
for i in range(size // 2 - 1, -1, -1):
_sift_down(a, lo, i, size)
for end in range(size - 1, 0, -1):
a[lo], a[lo + end] = a[lo + end], a[lo]
_sift_down(a, lo, 0, end)
def _median_index(a: list[T], i: int, j: int, k: int) -> int:
if a[j] < a[i]:
i, j = j, i
if a[k] < a[j]:
j = k
if a[j] < a[i]:
j = i
return j
def hoare_partition(a: list[T], p: int, r: int) -> int:
"""Split a[p..r] at j, p <= j < r, so that a[p..j] <= x <= a[j+1..r], x = a[p]."""
x = a[p] # @line L11
i, j = p - 1, r + 1
while True: # @line L12
j -= 1 # @line L13
while x < a[j]:
j -= 1
i += 1 # @line L14
while a[i] < x:
i += 1
if i < j: # @line L15
a[i], a[j] = a[j], a[i]
else:
return j
def _intro(a: list[T], lo: int, hi: int, d: int) -> None:
while hi - lo > SMALL: # @line L2
if d == 0: # @line L3
_heapsort(a, lo, hi)
return
d -= 1 # @line L4
m = _median_index(a, lo, (lo + hi) // 2, hi - 1) # @line L5
a[lo], a[m] = a[m], a[lo] # @line L6
j = hoare_partition(a, lo, hi - 1) # @line L7
if j + 1 - lo < hi - j - 1: # @line L8
_intro(a, lo, j + 1, d)
lo = j + 1
else: # @line L9
_intro(a, j + 1, hi, d)
hi = j + 1
_insertion_sort(a, lo, hi) # @line L10
def introsort(a: list[T]) -> None:
"""Sort a in place in non-decreasing order.
Quicksort with a median-of-three pivot and Hoare partitioning, which
switches a range to heapsort when the recursion is deeper than 2 lg n,
and sorts ranges of at most 16 items by insertion sort.
Cost: O(n log n) worst case, O(log n) stack. Not stable.
"""
n = len(a)
if n > 1: # @line L1
_intro(a, 0, n, 2 * (n.bit_length() - 1))
test_introsort.py 126 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/introsort/. The authors are listed in prov/S172EG.jsonl.
import itertools
import random
import introsort as module
from introsort import hoare_partition, introsort
class Key:
def __init__(self, k: int, tag: int) -> None:
self.k, self.tag = k, tag
def __lt__(self, other: "Key") -> bool:
return self.k < other.k
EXAMPLE = [13, 2, 19, 7, 5, 17, 11, 3, 20, 1, 15, 9, 6, 18, 4, 12, 16, 8, 14, 10]
def test_example() -> None:
a = list(EXAMPLE)
introsort(a)
assert a == list(range(1, 21))
def test_example_partition() -> None:
a = list(EXAMPLE)
j = hoare_partition(a, 0, 19)
assert j == 11
assert a == [10, 2, 8, 7, 5, 12, 11, 3, 4, 1, 6, 9, 15, 18, 20, 17, 16, 19, 14, 13]
def test_edges() -> None:
for a in ([], [1], [2, 1], [1, 2], [1, 1, 1], [3, 2, 1], [2**63 - 1, -(2**63)], [2**63 - 1, 0, -(2**63), 2**63 - 1]):
b = list(a)
introsort(b)
assert b == sorted(a)
def test_patterns() -> None:
n = 3000
for a in (list(range(n)), list(range(n, 0, -1)), [7] * n, [i % 3 for i in range(n)], list(range(n // 2)) + list(range(n // 2, 0, -1))):
b = list(a)
introsort(b)
assert b == sorted(a)
def test_all_permutations_of_small_and_cutoff_sizes() -> None:
for n in range(7):
for p in itertools.permutations(range(n)):
b = list(p)
introsort(b)
assert b == list(range(n))
rng = random.Random(16)
for n in (16, 17, 18, 33, 34):
for _ in range(50):
a = [rng.randint(0, 5) for _ in range(n)]
b = list(a)
introsort(b)
assert b == sorted(a)
def test_heapsort_fallback_on_killer_input() -> None:
# McIlroy's adversary against median-of-3 quicksort, run lazily.
n = 600
val: list[int | None] = [None] * n
state = {"solid": 0, "cand": -1}
class Gas:
def __init__(self, i: int) -> None:
self.i = i
def __lt__(self, other: "Gas") -> bool:
x, y = self.i, other.i
if val[x] is None and val[y] is None:
z = x if x == state["cand"] else y
val[z] = state["solid"]
state["solid"] += 1
if val[x] is None:
state["cand"] = x
elif val[y] is None:
state["cand"] = y
vx = n if val[x] is None else val[x]
vy = n if val[y] is None else val[y]
return vx < vy
used = []
original = module._heapsort
def counting_heapsort(a: list, lo: int, hi: int) -> None:
used.append(hi - lo)
original(a, lo, hi)
module._heapsort = counting_heapsort
try:
g = [Gas(i) for i in range(n)]
introsort(g)
finally:
module._heapsort = original
assert all(not g[i + 1] < g[i] for i in range(n - 1))
assert sum(used) > n // 2
def test_not_stable() -> None:
v = [0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1]
a = [Key(k, i) for i, k in enumerate(v)]
introsort(a)
assert [e.k for e in a] == sorted(v)
assert [e.tag for e in a] == [15, 14, 13, 9, 0, 5, 4, 1, 8, 6, 7, 3, 10, 11, 12, 2, 16]
def test_random_against_sorted() -> None:
rng = random.Random(1997)
for _ in range(600):
a = [rng.randint(-50, 50) for _ in range(rng.randint(0, 120))]
b = list(a)
introsort(b)
assert b == sorted(a)
def test_strings() -> None:
a = ["pear", "fig", "apple", "fig", "kiwi"] * 5
introsort(a)
assert a == sorted(["pear", "fig", "apple", "fig", "kiwi"] * 5)
What the next level needs
- the tests did not run in this build