Batcher Merge-Exchange Sort

Question

Does anyone have a good guide / explanation for sorting the Mercher-Exchange Batcher?

This is not the same algorithm as Batcher bit-sorting, or sorting with the odd, uniform Batcher method, although many articles pretend to be so.

Answer 1

Donald Knuth, The Art of Programming, 5.2.2M Algorithm (Volume III, p. 111).

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

Answer 2

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 = 2T-1, 2T-2, 2T-3, ..., 1 do
R = 0, D = P
for Q = 2T-1, 2T-2, 2T-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

Answer 3

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);
}