Sorting Networks
When sorting lists of some specific size, sorting networks are often employed. These are very simple devices that only do compareexchange operations. A compareexchange operation on the pair <x, y> is merely the following code.
if x > y then {t = x; x = y; y = t}
Consider the network example in figure 1.
Figure 1  A FourElement Sorting Network
Here is how it works. The pairs of blue dots are modules that perform compareexchange operations. Thus, in the first column, the pairs of numbers <3, 8> and <6, 2> enter the modules where the 6 and 2 are exchanged while the 3 and 8 remain in their original positions. Tracing the numbers as they go through the network provides the following table.
3 
3 
2 
2 
2 
8 
8 
8 
6 
3 
6 
2 
3 
3 
6 
2 
6 
6 
8 
8 
Note that the first column of modules exchanged the <6, 2> pair, the second column exchanged the <3, 2> pair, then the pair <8, 6> was exchanged, and finally the pair <6, 3> was exchanged.
Now that we know how it works, we need to explore why it works and what strategy motivated the design of the network. Understanding why generalizations of the above sorting network are correct is nontrivial.
Networks similar to that of figure 1 are derived from a strange mergesort algorithm developed by K. E. Batcher in the 1960's. Thus it is known as Batcher's OddEven Mergesort algorithm. The main sorting algorithm is exactly the same as the standard mergesort presented in figure 2.
Figure 2  Mergesort
The only difference is in the merge. In our first presentation of the merge, we shall assume that the two lists to be merged are both of the same size and that this size is a power of two. We shall need two auxiliary methods or algorithms in our new merge. One is a shuffle operation on lists exactly like that used with playing cards and the other is the compare exchange operation. The specifications for these appear as figure 3 along with the specifications for merging.
Figure 3  Specifications
The strategy behind Batcher's oddeven merge is to merge the elements in the oddnumbered positions of lists a and b. That is, merge:
a[1], a[3], ... , a[n1] with b[1], b[3], ... , b[n1].
Then merge the elements of a and b that occupy the even numbered positions. After this, the two recently merged lists are shuffled and adjacent items are checked for proper order. Here is an example:
a = 5, 9, 14, 25 
b = 3, 12, 19, 32 

merge a_{o} = the odd elements of a with those of b 

a_{o} = 5, 14 
b_{o} = 3, 19 
c_{o} = 3, 5, 14, 19 
merge a_{e} = the even elements of a with those of b 

a_{e} = 9, 25 
b_{e} = 12, 32 
c_{e} = 9, 12, 25, 32 
shuffle c_{o} with c_{e} 

c = 3, 9, 5, 12, 14, 25, 19, 32 
Note that at this point exchanging adjacent elements of c provides us with a perfectly sorted list. The recursive algorithm appears in figure 4.
Figure 4  Batcher's OddEven Merge
The proof of correctness for this strange merge involves showing that each of the elements in c_{o} and c_{e} are larger than a certain number of elements of c. Since both a[1] and b[1] are in c_{o}, then we know that the first element of c_{o} is the smallest on the list. For c_{o}[i] and c_{e}[i1], an intricate counting argument shows that each is larger than 2i3 elements and thus should be in either position 2i2 or 2i1.
Deriving the complexity of this merge is not so difficult. We note that the shuffle and the compareexchange operations take O(n) operations and solve this recurance relation for merging two lists of size n.
Merge(n, n) = 2*Merge(n/2, n/2) + n
Since n is a power of two, we may rewrite and solve the equation as shown below.
Merge(2^{k}, 2^{k}) 
= 2*Merge(2^{k1}, 2^{k1}) + 2^{k} 

= 2*(2*Merge(2^{k2}, 2^{k2}) + 2^{k1}) + 2^{k} 

= 2^{2}*Merge(2^{k2}, 2^{k2}) + 2^{k} + 2^{k} 

= 2^{k} + ... + 2^{k} 

= k*2^{k} 

= nlogn 
This results in a complexity of O(n[logn]^{2}) for the mergesort algorithm using the oddeven merge. This is still much better than O(n^{2}).
Two important observations lead from the oddeven mergesort to sorting networks.
So, if we note the order of the compareexchange operations during a sort, we can easily construct a sorting network and even build a sorting circuit. The compareexchange operations for a list of size four are:
merge the first two elements: 
compex(a, 1, 2) 
merge the last two elements: 
compex(a, 3, 4) 
merge the odd elements: 
compex(a, 1, 3) 
merge the even elements: 
compex(a, 2, 4) 
shuffle and correct: 
compex(a, 2, 3) 
This produces the sorting network of figure 1. Omitting the operations that involve element 4 provides the sorting network for lists of size three shown in figure 5. It is easy to verify that this is correct.
Figure 5  A ThreeElement Sorting Network
If we wish to perform the oddeven mergesort on lists which are not powers of two in length, we do exactly the same thing that we would do in order to mergesort such a list. Consider the operations that we would go through to sort a list of size five.
Extracting the compareexchange operations provides both a straight line algorithm and a sorting network for lists of five elements. The network is shown in figure 6.
Figure 6  A FiveElement Sorting Network