Sorting Networks

When sorting lists of some specific size, sorting networks are often employed. These are very simple devices that only do compare-exchange operations. A compare-exchange 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 Four-Element Sorting Network

Here is how it works. The pairs of blue dots are modules that perform compare-exchange 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 Odd-Even 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 odd-even merge is to merge the elements in the odd-numbered positions of lists a and b. That is, merge:

a[1], a[3], ... , a[n-1] with b[1], b[3], ... , b[n-1].

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 ao = the odd elements of a with those of b

ao = 5, 14

bo = 3, 19

co = 3, 5, 14, 19

merge ae = the even elements of a with those of b

ae = 9, 25

be = 12, 32

ce = 9, 12, 25, 32

shuffle co with ce

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 Odd-Even Merge

The proof of correctness for this strange merge involves showing that each of the elements in co and ce are larger than a certain number of elements of c. Since both a[1] and b[1] are in co, then we know that the first element of co is the smallest on the list. For co[i] and ce[i-1], an intricate counting argument shows that each is larger than 2i-3 elements and thus should be in either position 2i-2 or 2i-1.

Deriving the complexity of this merge is not so difficult. We note that the shuffle and the compare-exchange 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(2k, 2k)

= 2*Merge(2k-1, 2k-1) + 2k

 

= 2*(2*Merge(2k-2, 2k-2) + 2k-1) + 2k

 

= 22*Merge(2k-2, 2k-2) + 2k + 2k

 

= 2k + ... + 2k

 

= k*2k

 

= nlogn

This results in a complexity of O(n[logn]2) for the mergesort algorithm using the odd-even merge. This is still much better than O(n2).

Two important observations lead from the odd-even mergesort to sorting networks.

So, if we note the order of the compare-exchange operations during a sort, we can easily construct a sorting network and even build a sorting circuit. The compare-exchange 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 Three-Element Sorting Network

If we wish to perform the odd-even 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.

divide the list into (a[1],a[2],a[3]) and (a[4],a[5])
divide the first list into (a[1],a[2]) and (a[3])
merge a[1] and a[2]: compex(a, 1, 2)
now (a[1], a[2]) is sorted
form odd lists (a[1]) and (a[3])
merge a[1] and a[3]: compex(a, 1, 3)
shuffle (a[1],a[3]) and (a[2]) to get (a[1],a[2],a[3])
correct (a[1],a[2],a[3]):
compex(a, 2, 3)
now (a[1], a[2], a[3]) is sorted
merge a[4] and a[5]: compex(a, 4, 5)
now (a[1], a[2], a[3]) and (a[4], a[5]) are sorted
form odd lists (a[1],a[3]) and (a[4])
form odd lists (a[1]) and (a[4])
merge a[1] and a[4]: compex(a, 1, 4)
shuffle (a[1],a[4]) and (a[3]) to get (a[1], a[3], a[4])
correct (a[1],a[3],a[4]):
compex(a, 3, 4)
now (a[1], a[3], a[4]) is sorted
form even list (a[2], a[5])
merge a[2] and a[5]: compex(a, 2, 5)
now (a[1], a[3], a[4]) and (a[2], a[5]) are sorted
shuffle (a[1],a[3],a[4]) and (a[2],a[5]) to get (a[1],a[2],a[3],a[5],a[4])
correct (a[1],a[2],a[3],a[4],a[5]):
compex(a, 2, 3); compex(a, 4, 5)

Extracting the compare-exchange 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 Five-Element Sorting Network