Pairwise sorting network in Python

Parberry's network that sorts pairs, sorts the first and second items of the pairs, and then sorts the sorted pairs, with exactly the size and depth of odd-even merge sort.

File: pairwise_sorting_network.py, 48 lines
Level: I0 not checked yet
Toolchain: Python 3.14, pytest 9
Test framework: pytest
Run the tests: python3 -m pytest

pairwise_sorting_network.pyRaw GitHub

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/pairwise-sorting-network/. The authors are listed in prov/Y3SNG1.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, r: int) -> None:
    """Append the comparators that sort the wires lo, lo + r, ..., lo + m - r."""
    if r >= m:  # @line L1
        return
    for i in range(lo, lo + m, 2 * r):  # @line L2: sort each pair
        net.append((i, i + r))
    _sort(net, lo, m, 2 * r)  # @line L3: the first items of the pairs
    _sort(net, lo + r, m, 2 * r)  # @line L4: the second items of the pairs
    k = m // (2 * r)  # @line L5: the number of pairs
    g = k // 2  # @line L6
    while g >= 1:  # @line L7
        for i in range(k - g):  # @line L8: b_i against a_(i+g)
            net.append((lo + (2 * i + 1) * r, lo + 2 * (i + g) * r))
        g //= 2  # @line L9


def pairwise_network(n: int) -> list[tuple[int, int]]:
    """Return the comparators (i, j), i < j, of Parberry's pairwise sorting network 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, 1)
    return [(i, j) for i, j in net if j < n]


def pairwise_sorting_network(a: list[T]) -> None:
    """Sort a in place, in non-decreasing order, with the pairwise sorting network."""
    for i, j in pairwise_network(len(a)):
        if a[j] < a[i]:  # @line L10
            a[i], a[j] = a[j], a[i]

test_pairwise_sorting_network.py 56 lines

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/pairwise-sorting-network/. The authors are listed in prov/Y3SNG1.jsonl.

import itertools
import random

from pairwise_sorting_network import pairwise_network, pairwise_sorting_network


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]
    pairwise_sorting_network(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)
        pairwise_sorting_network(b)
        assert b == sorted(a)


def test_size_and_depth_match_batcher() -> None:
    for k in range(1, 7):
        n = 2**k
        net = pairwise_network(n)
        assert len(net) == 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 = pairwise_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(1992)
    for _ in range(600):
        a = [rng.randint(-40, 40) for _ in range(rng.randint(0, 70))]
        b = list(a)
        pairwise_sorting_network(b)
        assert b == sorted(a)

What the next level needs

the tests did not run in this build

Read the full page about Pairwise sorting network