Bitonic sort in Python
Batcher's network that sorts by recursively building and merging bitonic sequences, with O(log^2 n) depth.
- File
bitonic_sort.py, 56 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/bitonic-sort/. The authors are listed in prov/TD72MA.jsonl.
from typing import Protocol, TypeVar
class Ordered(Protocol):
def __lt__(self, other: "Ordered", /) -> bool: ...
T = TypeVar("T", bound=Ordered)
def _sort(net: list[tuple[int, int]], lo: int, m: int) -> None:
"""Append the comparators of BITONIC-SORT on wires lo .. lo + m - 1."""
if m <= 1: # @line L1
return
h = m // 2 # @line L2
_sort(net, lo, h) # @line L3
_sort(net, lo + h, h) # @line L4
for t in range(h): # @line L5: the flip
net.append((lo + t, lo + m - 1 - t))
_half_cleaners(net, lo, h) # @line L6
_half_cleaners(net, lo + h, h) # @line L7
def _half_cleaners(net: list[tuple[int, int]], lo: int, m: int) -> None:
"""Append the comparators that sort a bitonic part on wires lo .. lo + m - 1."""
if m <= 1: # @line L8
return
h = m // 2 # @line L9
for t in range(h): # @line L10
net.append((lo + t, lo + t + h))
_half_cleaners(net, lo, h) # @line L11
_half_cleaners(net, lo + h, h) # @line L12
def bitonic_network(n: int) -> list[tuple[int, int]]:
"""Return the comparators (i, j), i < j, of bitonic sort on n wires.
For n not a power of 2, build the network for the next power of 2 and
drop each comparator that touches a wire j >= n.
"""
size = 1
while size < n:
size *= 2
net: list[tuple[int, int]] = []
_sort(net, 0, size)
return [(i, j) for i, j in net if j < n]
def bitonic_sort(a: list[T]) -> None:
"""Sort a in place, in non-decreasing order, with the bitonic network."""
for i, j in bitonic_network(len(a)):
if a[j] < a[i]: # @line L13
a[i], a[j] = a[j], a[i]
test_bitonic_sort.py 56 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/bitonic-sort/. The authors are listed in prov/TD72MA.jsonl.
import itertools
import random
from bitonic_sort import bitonic_network, bitonic_sort
def depth(net: list[tuple[int, int]], n: int) -> int:
level = [0] * n
for i, j in net:
level[i] = level[j] = max(level[i], level[j]) + 1
return max(level, default=0)
def test_example() -> None:
a = [3, 7, 4, 8, 6, 2, 1, 5]
bitonic_sort(a)
assert a == [1, 2, 3, 4, 5, 6, 7, 8]
def test_edges() -> None:
for a in ([], [1], [2, 1], [1, 1, 1], [3, 2, 1], [1, 2, 3], [5, 5, 4, 4, 3]):
b = list(a)
bitonic_sort(b)
assert b == sorted(a)
def test_size_and_depth() -> None:
for k in range(1, 7):
n = 2**k
net = bitonic_network(n)
assert len(net) == n * k * (k + 1) // 4
assert depth(net, n) == k * (k + 1) // 2
assert all(i < j for i, j in net)
def test_all_zero_one_inputs() -> None:
for n in range(1, 11):
net = bitonic_network(n)
for bits in itertools.product((0, 1), repeat=n):
b = list(bits)
for i, j in net:
if b[j] < b[i]:
b[i], b[j] = b[j], b[i]
assert b == sorted(bits)
def test_random_against_sorted() -> None:
rng = random.Random(1968)
for _ in range(600):
a = [rng.randint(-40, 40) for _ in range(rng.randint(0, 70))]
b = list(a)
bitonic_sort(b)
assert b == sorted(a)
What the next level needs
- the tests did not run in this build