Sorting networks

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 oddevenmergesort)?

• Could it be implemented without recursion?

My code:

```
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

Your naming could be improved. x, i and j are pretty uniformative and they mean very different things. x should definitely be changed to something more descriptive. Maybe collection, data or source? x often is used for a single value so it's not immediately obvious that it's taking a list. The name comparator also sounds like it's checking for something, not modifying in place. check_swap could be an improvement. It's not 100% clear, however it indicates better what it does (check and swap) so that the user is less likely to make an incorrect assumption.

You should test for None with if indexes is None, as that's more Pythonic than == None.

At the end of oddevenmerge you could get both indexes simultaneously instead of having to refer to them. Consider using:

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

zip allows you to iterate over two lists simultaneously by producing two item tuples from each index of the lists. In your case, it's actually iterating over the same list, but from two different places. This saves you a less readable range construct and means that i and j can be assigned more directly.

StackExchange Code Review Q#112448, answer score: 3