algorithmsortingmergesorting-network

Optimal Batcher odd-even merge networks for sizes different than 2^n

These days, I have been trying to implement sorting networks up to size 32 with a minimal number of compare-exchange units (optimal in size, not in depth). As of now, I have been able to use the following resources to generate my networks:

The paper Finding Better Sorting Networks by Baddar gives the minimal number of compare-exchange units known to be needed for sorting networks 0 to 32 (not up-to-date since Valsalam and Miikkulainen provide better algorithms for the sizes 17, 18, 19, 20, 21 and 22) and the method used to find them: basically, one has to split the array to sort in two, then sort both halves using the best known sorting networks for these sizes before merging them using an odd-even merge network (which corresponds to the merge step of Batcher's odd-even mergesort).

The Wikipedia page gives the following Python implementation for Batcher's odd-even mergesort:

def oddeven_merge(lo, hi, r):
    step = r * 2
    if step < hi - lo:
        yield from oddeven_merge(lo, hi, step)
        yield from oddeven_merge(lo + r, hi, step)
        yield from [(i, i + r) for i in range(lo + r, hi - r, step)]
    else:
        yield (lo, lo + r)

def oddeven_merge_sort_range(lo, hi):
    """ sort the part of x with indices between lo and hi.

    Note: endpoints (lo and hi) are included.
    """
    if (hi - lo) >= 1:
        # if there is more than one element, split the input
        # down the middle and first sort the first and second
        # half, followed by merging them.
        mid = lo + ((hi - lo) // 2)
        yield from oddeven_merge_sort_range(lo, mid)
        yield from oddeven_merge_sort_range(mid + 1, hi)
        yield from oddeven_merge(lo, hi, 1)

def oddeven_merge_sort(length):
    """ "length" is the length of the list to be sorted.
    Returns a list of pairs of indices starting with 0 """
    yield from oddeven_merge_sort_range(0, length - 1)

The oddeven_merge step is already isolated, so it was easy to use it alone to generate the pairs of indices needed to merge the two sorted halves of the original array. However, this implementation only works when the size of the array is a power of 2. Therefore, it only allowed me to find the minimal known number of compare-exchange units needed for a sorting network of size 32. Removing the indices pairs with the highest index allowed me to find the equivalent sorting network of size 31, but removing more pairs didn't yield the best known results for sizes smaller than 31.

Perl's Algorithm::Networksort module provides an alternative Batcher's odd-even mergesort implementation that works with arrays of any size, not only powers of 2. Therefore, I decided to have a look at it to see whether I could extract the merging step from the algorithm. Here is the Python equivalent (it also corresponds to the algorithm as described by Knuth in The Art of Computer Programming vol. 3):

def oddeven_merge_sort(length):
    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:
                    yield (i, i + d)

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

Unfortunately, this algorithm seems a bit cryptic to my eyes, and I wasn't able to extract the merging part from it at all. I managed to derive a merging network that gave me the minimal known number of compare-exchange units needed for a sorting network of size 24 but the trick I used didn't scale to any other sizes (and from my understanding, it was definitely not an odd-even merge).

I have tried a couple more things to adapt the merge step from Batcher's odd-even mergesort for arrays whose size is not a power of two, but I wasn't able to find the best-known sorting networks for sizes 25, 26, 27, 28, 29 and 30. How can I derive this merge step to find the missing pieces of the puzzle?

Solution

  • The Perl algorithm mentions in a comment that it's algorithm 5.2.2M in Knuth's Searching and Sorting.

    In turn, Knuth mentions that it merges the sorted sequences together with when p = 1. So to generate your pairs that merge the sequence for any N you simply run the algorithm with p = 1:

    def oddeven_merge_step(length):
    t = math.ceil(math.log2(length))
    q = 2 ** (t - 1)
    r = 0
    d = 1

    while d > 0:
        for i in range(length - d):
            if i & 1 == r:
                yield (i, i + d)

        d = q - 1
        q //= 2
        r = 1

    Note that Batcher's Odd-Even merge step expects the sorted sequences interleaved (even, odd, even, ...), but produces a sorted sequence that is contiguous.

    For example for N = 25 it generates the following network:

    network