Odd-even merge sort in Python
Batcher's network that sorts by recursively merging sorted halves with odd-even merges, with O(log^2 n) depth.
- File
odd_even_merge_sort.py, 54 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/odd-even-merge-sort/. The authors are listed in prov/0H3K90.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 OEM-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
_merge(net, lo, m, 1) # @line L5
def _merge(net: list[tuple[int, int]], lo: int, m: int, r: int) -> None:
"""Append the comparators that merge the two sorted halves of the wires lo, lo + r, ..., lo + m - r."""
s = 2 * r # @line L6
if s < m: # @line L7
_merge(net, lo, m, s) # @line L8
_merge(net, lo + r, m, s) # @line L9
for i in range(lo + r, lo + m - r, s): # @line L10
net.append((i, i + r))
else:
net.append((lo, lo + r)) # @line L11
def odd_even_merge_network(n: int) -> list[tuple[int, int]]:
"""Return the comparators (i, j), i < j, of odd-even merge 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 odd_even_merge_sort(a: list[T]) -> None:
"""Sort a in place, in non-decreasing order, with Batcher's odd-even merge network."""
for i, j in odd_even_merge_network(len(a)):
if a[j] < a[i]: # @line L12
a[i], a[j] = a[j], a[i]
test_odd_even_merge_sort.py 57 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/odd-even-merge-sort/. The authors are listed in prov/0H3K90.jsonl.
import itertools
import random
from odd_even_merge_sort import odd_even_merge_network, odd_even_merge_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 = [1, 6, 8, 3, 2, 7, 5, 4]
odd_even_merge_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)
odd_even_merge_sort(b)
assert b == sorted(a)
def test_size_and_depth() -> None:
sizes = {2: 1, 4: 5, 8: 19, 16: 63, 32: 191, 64: 543}
for k in range(1, 7):
n = 2**k
net = odd_even_merge_network(n)
assert len(net) == sizes[n] == n * k * (k - 1) // 4 + n - 1
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, 13):
net = odd_even_merge_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)
odd_even_merge_sort(b)
assert b == sorted(a)
What the next level needs
- the tests did not run in this build