Source

sorting_network / sorting_net.py

Full commit
def comparator(x, y):
    mn = min(x, y)
    mx = max(x, y)
    return mn, mx

def separate(seq):
    n = len(seq) // 2
    return seq[:n], seq[n:]

def half_cleaner(seq, merge = True):
    if len(seq) == 1:
        return seq
    left, right = separate(seq)
    result = [comparator(*x) for x in zip(left, right)]
    left, right = [list(x) for x in zip(*result)]
    if merge:
        return left + right
    else:
        return left, right

def bitonic_sorter(seq):
    if len(seq) <= 1:
        return seq
    left, right = half_cleaner(seq, False)
    return bitonic_sorter(left) + bitonic_sorter(right)

def merger(seq):
    left, right = separate(seq)
    zipped = [comparator(*x) for x in zip(left, reversed(right))]
    left, right = zip(*zipped)
    return bitonic_sorter(left) + bitonic_sorter(right)

def sorter(seq):
    if len(seq) == 1:
        return seq
    if len(seq) == 2:
        return list(comparator(seq[0], seq[1]))
    left, right = separate(seq)
    return merger(sorter(left) + sorter(right))