9
\$\begingroup\$

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.

https://upload.wikimedia.org/wikipedia/commons/thumb/9/9b/SimpleSortingNetworkFullOperation.svg/800px-SimpleSortingNetworkFullOperation.svg.png

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:

  1. Is there a neater way to do it without passing the lists of indexes arround?
  2. Is there a hack (other than padding) to make it work with lists length not a power of 2?
  3. Can Python be made to do any parallelism (perhaps the recursive calls to oddevenmergesort)?
  4. 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 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)
\$\endgroup\$
  • \$\begingroup\$ Tip: Read about zip() \$\endgroup\$ – Piotr Nawrot Dec 1 '15 at 15:16
  • \$\begingroup\$ @ColonelPanic Yes, it does. If this was Python 2 I would have had a couple other suggestions, but they're not relevant to 3. \$\endgroup\$ – SuperBiasedMan Dec 1 '15 at 17:17
  • \$\begingroup\$ @SuperBiasedMan presumably one about range returning a list? \$\endgroup\$ – Colonel Panic Dec 1 '15 at 17:50
  • \$\begingroup\$ @ColonelPanic Precisely that, yes. \$\endgroup\$ – SuperBiasedMan Dec 1 '15 at 17:58
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

I actually had the same problem recently while trying to implement this algorithm. Unfortunately, I can't answer the whole question since I couldn't solve the problem of making this very algorithm work with any list whose size wasn't a power of 2 (the best you can do is probably sort a list of size e.g. 16+12 by running the algorithm for size 32 and dropping all the comparators features indices greater than 28).

Since I couldn't find how to make the Wikipedia version of the algorithm work with lists of any sizes (not the equivalent version passing the indices around), I decided to port to Python the algorithm found in Perl's Algorithm::Networksort which corresponds to Batcher's odd-even mergesort as described by Donald Knuth in The Art of Computer Programming. This is not a recursive approach and is somehow harder to reason about:

def oddeven_merge_sort(collection):
    length = len(collection)
    t = math.ceil(math.log2(length))

    p = 2 ** (t - 1)

    while p > 0:
        q = 2 ** (t - 1)
        r = 0
        d = p

        while d > 0:
            for i in range(length - d):
                if i & p == r:
                    comparator(collection, i, i + d)

            d = q - p
        q //= 2
        r = p
    p //= 2

I don't see why the recursive call to oddevenmergesort in your original algorithm couldn't be parallelized. Here is the untested relevant part of the code using the multiprocessing module:

p = multiprocessing.Process(target=oddevenmergesort, args=(x, indexes[:n//2]))
p.start()
oddevenmergesort(x, indexes[n//2:])
p.join()
oddevenmerge(x, indexes)

That said, the multiprocessing module would only make things faster for huge collections since the cost of launching a new process is really high. The threading module wouldn't help either since all of its "threads" actually run in a single processor thread. I don't know whether the other version I presented can run in parallel.

\$\endgroup\$
1
\$\begingroup\$
  1. You could create the index list explicitly each step by using the partner function in the wikipedia article

  2. You can change comparator to not do anything if either of the 2 indices are out of range and round up the array length to the next power of two when initializing.

    def comparator(x, i, j):
        """Swap x[i] and x[j] if they are out of order"""
        if i < len(x) and j < len(x) and x[i] > x[j]:
            x[i], x[j] = x[j], x[i]
    
  3. The part to parallelize is the for loop in oddevenmerge

  4. see 1

\$\endgroup\$
  • \$\begingroup\$ Ad 2. itertools.zip_longest() \$\endgroup\$ – Piotr Nawrot Dec 2 '15 at 0:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.