Batcher's Merge-Exchange Sort

Question

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.

Answer 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.

Answer 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.