Radix sort (LSD) in Python
Sorts keys digit by digit from least to most significant using a stable sort on each digit.
- File
radix_sort.py, 42 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/radix-sort/. The authors are listed in prov/HB6K6X.jsonl.
from typing import Callable, TypeVar
T = TypeVar("T")
def _counting_sort_by(a: list[T], b: int, digit: Callable[[T], int]) -> list[T]:
"""Stable counting sort of a by digit(x), which is in 0 .. b - 1."""
c = [0] * b
for x in a:
c[digit(x)] += 1
s = 0
for v in range(b):
c[v], s = s, s + c[v]
out: list[T | None] = [None] * len(a)
for x in a:
v = digit(x)
out[c[v]] = x
c[v] += 1
return out # type: ignore[return-value]
def radix_sort(a: list[T], b: int = 256, key: Callable[[T], int] = lambda x: x) -> list[T]: # type: ignore[assignment,return-value]
"""Return a new list with the items of a, stably sorted by key.
Precondition: each key is an integer >= 0, and b >= 2. The cost is
Theta(d (n + b)) time, where d is the number of base-b digits of the
largest key, and Theta(n + b) extra space.
"""
if b < 2:
raise ValueError("the base must be at least 2")
m = max((key(x) for x in a), default=0) # @line L1
p = 1 # @line L2
while True: # @line L3
q = p
a = _counting_sort_by(a, b, lambda x: (key(x) // q) % b) # @line L4
p *= b # @line L5
if p > m: # @line L6
break
return a # @line L7
test_radix_sort.py 34 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/radix-sort/. The authors are listed in prov/HB6K6X.jsonl.
import random
from radix_sort import radix_sort
def test_example() -> None:
a = [329, 457, 657, 839, 436, 720, 355]
assert radix_sort(a, 10) == [329, 355, 436, 457, 657, 720, 839]
def test_edges() -> None:
assert radix_sort([], 10) == []
assert radix_sort([0], 10) == [0]
assert radix_sort([0, 0, 0], 2) == [0, 0, 0]
assert radix_sort([10, 9, 100, 1], 10) == [1, 9, 10, 100]
big = [2**64 - 1, 0, 2**63, 1]
assert radix_sort(big) == sorted(big)
def test_stable() -> None:
a = [(5, "a"), (3, "b"), (5, "c"), (13, "d"), (3, "e")]
out = radix_sort(a, 2, key=lambda p: p[0])
assert [t for _, t in out] == ["b", "e", "a", "c", "d"]
def test_random_against_sorted() -> None:
rng = random.Random(4417)
for _ in range(600):
b = rng.choice([2, 3, 10, 16, 256])
a = [(rng.randrange(0, 10 ** rng.randint(1, 6)), j) for j in range(rng.randint(0, 40))]
assert radix_sort(a, b, key=lambda p: p[0]) == sorted(a, key=lambda p: p[0])
What the next level needs
- the tests did not run in this build