Tournament sort in Python
Selection sort using a tournament tree of comparisons to find each successive minimum.
- File
tournament_sort.py, 51 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/tournament-sort/. The authors are listed in prov/15RWNV.jsonl.
from typing import Protocol, TypeVar
class Ordered(Protocol):
def __lt__(self, other: "Ordered", /) -> bool: ...
T = TypeVar("T", bound=Ordered)
EMPTY = -1
def tournament_sort(a: list[T]) -> int:
"""Sort the list a stably, with a winner tree. Return the number of comparisons."""
n = len(a)
if n < 2:
return 0
count = 0
def winner(i: int, j: int) -> int:
# The index of the winning item; an empty slot loses, and a tie goes to the left (smaller index).
nonlocal count
if i == EMPTY:
return j
if j == EMPTY:
return i
count += 1
return j if a[j] < a[i] else i
m = 1 # @line L1
while m < n:
m *= 2
tree = [EMPTY] * (2 * m)
for i in range(n):
tree[m + i] = i
for v in range(m - 1, 0, -1): # @line L2
tree[v] = winner(tree[2 * v], tree[2 * v + 1])
out: list[T] = []
for _ in range(n): # @line L3
w = tree[1] # @line L4
out.append(a[w])
v = m + w # @line L5
tree[v] = EMPTY
while v > 1: # @line L6
v //= 2 # @line L7
tree[v] = winner(tree[2 * v], tree[2 * v + 1])
a[:] = out # @line L8
return count
test_tournament_sort.py 55 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/tournament-sort/. The authors are listed in prov/15RWNV.jsonl.
import math
import random
from tournament_sort import tournament_sort
def test_example() -> None:
a = [5, 1, 4, 2, 8, 3, 7, 6]
assert tournament_sort(a) == 15
assert a == [1, 2, 3, 4, 5, 6, 7, 8]
def test_comparison_bound() -> None:
rng = random.Random(1)
for n in (2, 3, 7, 8, 9, 100, 1000):
a = list(range(n))
rng.shuffle(a)
c = tournament_sort(a)
assert a == list(range(n))
assert c <= (n - 1) + (n - 1) * math.ceil(math.log2(n))
def test_edges() -> None:
for a in ([], [1], [2, 1], [1, 1, 1], [3, 2, 1]):
b = list(a)
tournament_sort(b)
assert b == sorted(a)
def test_stable() -> None:
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
rng = random.Random(4)
for _ in range(200):
pairs = [(rng.randint(0, 4), i) for i in range(rng.randint(0, 40))]
b = [Key(k, t) for k, t in pairs]
tournament_sort(b)
assert [(x.k, x.tag) for x in b] == sorted(pairs)
def test_random_against_sorted() -> None:
rng = random.Random(6)
for _ in range(100):
a = [rng.randint(-50, 50) for _ in range(rng.randint(0, 300))]
b = list(a)
tournament_sort(b)
assert b == sorted(a)
What the next level needs
- the tests did not run in this build