Pigeonhole sort in Python
Places each key into a hole indexed by its value, then reads the holes in order; O(n+range) time.
- File
pigeonhole_sort.py, 29 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/pigeonhole-sort/. The authors are listed in prov/Y6SQW0.jsonl.
from collections import deque
from typing import Callable, TypeVar
T = TypeVar("T")
def pigeonhole_sort(a: list[T], key: Callable[[T], int] = lambda x: x) -> None: # type: ignore[assignment,return-value]
"""Sort the list a in place by its integer keys. The sort is stable.
The cost is Theta(n + k) time and Theta(n + k) extra space, where k is
max(key) - min(key) + 1. The caller must make sure that k is small.
"""
n = len(a)
if n == 0: # @line L1
return
keys = [key(x) for x in a]
lo, hi = min(keys), max(keys) # @line L2
k = hi - lo + 1 # @line L3
holes: list[deque[T]] = [deque() for _ in range(k)] # @line L4
for i in range(n): # @line L5
holes[keys[i] - lo].append(a[i]) # @line L6
j = 0 # @line L7
for h in range(k): # @line L8
for x in holes[h]: # @line L9
a[j] = x # @line L10
j += 1
test_pigeonhole_sort.py 34 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/pigeonhole-sort/. The authors are listed in prov/Y6SQW0.jsonl.
import random
from pigeonhole_sort import pigeonhole_sort
def test_example() -> None:
a = [8, 3, 2, 7, 4, 6, 8, 3]
pigeonhole_sort(a)
assert a == [2, 3, 3, 4, 6, 7, 8, 8]
def test_edges() -> None:
for a in ([], [5], [1, 1, 1], [-3, 4, -3, 0], [2, 1]):
b = list(a)
pigeonhole_sort(b)
assert b == sorted(a)
def test_stable() -> None:
a = [(3, "a"), (1, "b"), (3, "c"), (2, "d"), (1, "e")]
pigeonhole_sort(a, key=lambda p: p[0])
assert [t for _, t in a] == ["b", "e", "d", "a", "c"]
def test_random_against_sorted() -> None:
rng = random.Random(7712)
for _ in range(600):
a = [(rng.randint(-20, 20), j) for j in range(rng.randint(0, 50))]
b = list(a)
pigeonhole_sort(b, key=lambda p: p[0])
assert b == sorted(a, key=lambda p: p[0])
What the next level needs
- the tests did not run in this build