Yesterday I read a fascinating article on Wikipedia about sorting networks.
Comparator networks are abstract devices built up of a fixed number of "wires" carrying values, and comparator modules that connect pairs of wires, swapping the values on the wires if they are not in a desired order. Sorting networks differ from general comparison sorts in that they are not capable of handling arbitrarily large inputs, and in that their sequence of comparisons is set in advance, regardless of the outcome of previous comparisons.
The boon of the constraints is such algorithms are easy to build and parallelise in hardware.
The article lists several constructions of sorting networks. It's easy enough to see how the 'insertion sort' inspired network will always give the correct result, but the other constructions aren't so obvious.
As an exercise to myself, I ran Batcher's odd-even mergesort on paper (n=16) and tried implementing it in Python (as an in-place sort). I think my code works correctly, but some questions occured to me:
- Is there a neater way to do it without passing the lists of indexes arround?
- Is there a hack (other than padding) to make it work with lists length not a power of 2?
- Can Python be made to do any parallelism (perhaps the recursive calls to
- Could it be implemented without recursion?
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 r in range(1, len(indexes)-1, 2): i, j = indexes[r], indexes[r+1] comparator(x, i, j) unsorted = [3, 9, 2, 7, 1, 5, 8, 5, 2, 7, 1, 0, 2, 7, 5, 2] copy = list(unsorted) oddevenmergesort(copy) assert copy == sorted(unsorted)