Batcher's Merge-Exchange Sort

Does anyone have a good guide/explanation of Batcher's Merg开发者_JAVA技巧e-Exchange Sort?

This is not the same algorithm as Batcher's bitonic sort or Batcher's odd-even merge sort, though many articles pretend that it is.

Donald Knuth, The Art of Computer Programming, algorithm 5.2.2M (volume III, page 111).

Ken Batcher (1968), "Sorting networks and their application", Proc. AFIPS Spring Joint Computer Conference 32:307–314.

So after much thought I have somewhat of an answer. One thing that threw me off a little is that K.E. Batcher on his university its site itself mentions that he is the discoverer of two sorting algorithms; "the odd-even mergesort and the bitonic mergesort", referring to his 1968 Paper. (http://www.cs.kent.edu/~batcher/ and http://www.cs.kent.edu/~batcher/sort.pdf)

I think the confusion arises because the odd-even mergesort (as described in the paper) is a merging network, not a sorting network. However, since the design can scale to larger and smaller merge networks, a sorting network is easily constructed with it. It would seem to me that this is often referred to as "Batcher's merge-exchange sort". It seems that Knuth in The Art of Computer Programming. Volume 3. Sorting and Searching. Second Edition coins the term when discussing "Algorithm M (Merge exchange)." (pg111)

Even wikipedia does it weirdly, describing the odd-even merging network (but really, multiple instantiations of it, forming the merge-exchange sorting network, if you will) as a sorting network. (https://en.wikipedia.org/wiki/Batcher_odd–even_mergesort)

What is not helping is that the term "mergesort" has some ambiguity which I have seen often used when discussing sorting networks. The ambiguity being: does it sort by merging, or does it merge sorted sequences ? Even published papers sometimes use the terms "sorting network" and "merging network" loosely. I suppose the term "merge network" is never strictly defined and has the same ambiguity.

Simple implementation :)

int FloorLog2(int value)
{
    int result = -1;
    for (int i = 1; i < value; i <<= 1, ++result);
    return result;
}

void BatcherSort(int* array, int length)
{
    int t = FloorLog2(length);
    int p0 = (1 << t);
    int p = p0;

    do
    {
        int q = p0;
        int r = 0;
        int d = p;

        while (r == 0 || q != p)
        {
            if (r != 0)
            {
                d = q - p;
                q >>= 1;
            }

            for (int i = 0; i < length - d; ++i)
            {
                if (((i & p) == r) && array[i] > array[i + d])
                {
                    int swap = array[i];
                    array[i] = array[i + d];
                    array[i + d] = swap;
                }
            }

            r = p;
        }

        p >>= 1;
    }
    while (p > 0);
}

From http://www.eli.sdsu.edu/courses/spring96/cs662/notes/batcher/batcher.html

Input: N and array A[1:N] of items to sort

set  T = Ceiling(lg(N))

for P = 2^(T-1), 2^(T-2), 2^(T-3), ..., 1 do
R = 0, D = P
for Q = 2^(T-1), 2^(T-2), 2^(T-3), ..., P do
for (K = 1 to N - D ) and ((K-1)   P) = R do in parallel
if A[K] > A[K + D] then
swap(A[K], A[K + D ])
end if
end for
D = Q - P
R = P
end for
end for


(K + 1)   P means logical and of K and P

If number of processors is less than N than the swap becomes a merge

This site has a visualization of this algorithm