sortingnetworks.py

def comparator(x, i, j):
    """Swap x[i] and x[j] if they are out of order"""
    if x[i] > x[j]:
        x[i], x[j] = x[j], x[i]

def oddevenmergesort(x, indexes=None):
    """In-place odd-even mergesort, applied to slice of x defined by indexes. Assumes len(x) is a power of 2. """
    if indexes == None:
        indexes = range(len(x))
    n = len(indexes)
    if n > 1:
        oddevenmergesort(x, indexes[:n//2])
        oddevenmergesort(x, indexes[n//2:])
        oddevenmerge(x, indexes)

def oddevenmerge(x, indexes=None):
    """Assuming the first and second half of x are sorted, in-place merge. Optionally restrict to slice of x defined by indexes."""
    if indexes == None:
        indexes = range(len(x))

    if len(indexes) == 2:
        i, j = indexes
        comparator(x, i, j)
        return

    oddevenmerge(x, indexes[::2])
    oddevenmerge(x, indexes[1::2])
    
    for i, j in zip(indexes[1::2], indexes[2::2]):
        comparator(x, i, j)

sequence = [3, 9, 2, 7, 1, 5, 8, 5, 2, 7, 1, 0, 2, 7, 5, 2]
copy = list(sequence)
oddevenmergesort(copy)
assert copy == sorted(sequence)

def bitonicsort(x, indexes=None):
    if indexes == None:
        indexes = range(len(x))
    n = len(indexes)

    if n > 2:
        bitonicsort(x, indexes[:n//2])
        bitonicsort(x, indexes[n//2:])

    dark(x, indexes)
    light(x, indexes[:n//2])
    light(x, indexes[n//2:])

def dark(x, indexes=None):
    if indexes == None:
        indexes = range(len(x))
    n = len(indexes)

    for i, j in zip(indexes[:n//2], indexes[::-1]):
        comparator(x, i, j)

def light(x, indexes=None):
    if indexes == None:
        indexes = range(len(x))
    n = len(indexes)

    if n == 1:
        return

    for i, j in zip(indexes[:n//2], indexes[n//2:]):
        comparator(x, i, j)

    light(x, indexes[:n//2])
    light(x, indexes[n//2:])

sequence = [3, 9, 2, 7, 1, 5, 8, 5, 2, 7, 1, 0, 2, 7, 5, 2]
copy = list(sequence)
bitonicsort(copy)
assert copy == sorted(sequence)