'Batcher's Merge-Exchange Sort

Does anyone have a good guide/explanation of Batcher's Merge-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.

algorithmsorting


Solution 1:[1]

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.

Solution 2:[2]

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.

Solution 3:[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);
}

Solution 4:[4]

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

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1
Solution 2
Solution 3 AlexMAS
Solution 4

Related Questions