In Part II, we examined sorting algorithms for serial computers (random-access machines, or RAM's) that allow only one operation to be executed at a time. In this chapter, we investigate sorting algorithms based on a comparison network model of computation in which many comparison operations can be performed simultaneously.

Sorting networks are comparison networks that always sort their inputs, so it makes sense to begin our discussion with comparison networks and their characteristics. A comparison network is comprised solely of wires and comparators. A * comparator*, shown in Figure 28.1 (a), is a device with two inputs,

x' = min(x, y) ,

y' = max(x, y) .

A * wire* transmits a value from place to place. Wires can connect the output of one comparator to the input of another, but otherwise they are either network input wires or network output wires. Throughout this chapter, we shall assume that a comparison network contains

Under the assumption that each comparator takes unit time, we can define the "running time" of a comparison network, that is, the time it takes for all the output wires to receive their values once the input wires receive theirs. Informally, this time is the largest number of comparators that any input element can pass through as it travels from an input wire to an output wire. More formally, we define the * depth* of a wire as follows. An input wire of a comparison network has depth 0. Now, if a comparator has two input wires with depths

A * sorting network* is a comparison network for which the output sequence is monotonically increasing (that is,

Professor Nielsen claims that if we add a comparator anywhere in a sorting network, the resulting network also sorts. Show that the professor is mistaken by adding a comparator to the network of Figure 28.2 in such a way that the resulting network does not sort every input permutation.

Prove that any sorting network on *n* inputs has depth at least lg *n*.

Prove that the number of comparators in any sorting network is at least (*n* lg *n*).

Consider the comparison network shown in Figure 28.3. Prove that it is in fact a sorting network, and describe how its structure is related to that of insertion sort (Section 1.1).

The * zero-one principle* says that if a sorting network works correctly when each input is drawn from the set {0,1}, then it works correctly on arbitrary input numbers. (The numbers can be integers, reals, or, in general, any set of values from any linearly ordered set.) As we construct sorting networks and other comparison networks, the zero-one principle will allow us to focus on their operation for input sequences consisting solely of 0's and 1's. Once we have constructed a sorting network and proved that it can sort all zero-one sequences, we shall appeal to the zero-one principle to show that it properly sorts sequences of arbitrary values.

min(f(x),f(y)) =f(min(x,y)) ,

max(f(x),f(y)) =f(max(x,y)) .

State and prove an analog of the zero-one principle for a decision-tree model. (*Hint:* Be sure to handle equality properly.)

The first step in our construction of an efficient sorting network is to construct a comparison network that can sort any * bitonic sequence:* a sequence that either monotonically increases and then monotonically decreases, or else monotonically decreases and then monotonically increases. For example, the sequences 1, 4, 6, 8, 3, 2 and 9, 8, 3, 2, 4, 6 are both bitonic. The zero-one sequences that are bitonic have a simple structure. They have the form 0

A bitonic sorter is comprised of several stages, each of which is called a * half-cleaner*. Each half-cleaner is a comparison network of depth 1 in which input line

When a bitonic sequence of 0's and 1's is applied as input to a half-cleaner, the half-cleaner produces an output sequence in which smaller values are in the top half, larger values are in the bottom half, and both halves are bitonic. In fact, at least one of the halves is * clean*--consisting of either all 0's or all 1's--and it is from this property that we derive the name "half-cleaner." (Note that all clean sequences are bitonic.) The next lemma proves these properties of half-cleaners.

By recursively combining half-cleaners, as shown in Figure 28.9, we can build a * bitonic sorter*, which is a network that sorts bitonic sequences. The first stage of BITONIC-SORTER[

How many bitonic sequences of 0's and 1's are there?

Show that BITONIC-SORTER[*n*], where *n* is an exact power of 2, contains (*n *lg *n*) comparators.

Prove the following analog of the zero-one principle for bitonic sorting networks: a comparison network that can sort any bitonic sequence of 0's and 1's can sort any bitonic sequence of arbitrary numbers.

Our sorting network will be constructed from * merging networks*, which are networks that can merge two sorted input sequences into one sorted output sequence. We modify BITONIC-SORTER[

Prove an analog of the zero-one principle for merging networks. Specifically, show that a comparison network that can merge any two monotonically increasing sequences of 0's and 1's can merge any two monotonically increasing sequences of arbitrary numbers.

Consider a merging network with inputs *a*_{1}, *a*_{2}, . . . , *a _{n}*, for

Prove that any merging network, regardless of the order of inputs, requires (*n* lg *n*) comparators.

We now have all the necessary tools to construct a network that can sort any input sequence. The sorting network SORTER[*n*] uses the merging network to implement a parallel version of merge sort from Section 1.3.1. The construction and operation of the sorting network are illustrated in Figure 28.12.

whose solution is *D(n)* = (lg^{2} *n*). Thus, we can sort *n* numbers in parallel in *O*(lg^{2} *n*) time.

How many comparators are there in SORTER[*n*]?

Show that the depth of SORTER[*n*] is exactly (lg *n*)(lg*n* + 1)/2.

We can sort the elements of an *m* X *m* matrix by repeating the following procedure *k* times:

1. Sort each odd-numbered row into monotonically increasing order.

2. Sort each even-numbered row into monotonically decreasing order.

3. Sort each column into monotonically increasing order.

28-1 Transposition sorting networks

A comparison network is a * transposition network* if each comparator connects adjacent lines, as in the network in Figure 28.3.

* a.* Show that any transposition network with

An * odd-even sorting network* on

* c.* Prove that the family of odd-even sorting networks is indeed a family of sorting networks.

28-2 Batcher's odd-even merging network

In Section 28.4, we saw how to construct a merging network based on bitonic sorting. In this problem, we shall construct an * odd-even merging network*. We assume that

* a.* Draw a 2

* c.* What is the depth of a 2

A * permutation network* on

For a long time, the question remained open as to whether a sorting network with depth *O*(lg *n*) exists. In 1983, the answer was shown to be a somewhat unsatisfying yes. The AKS sorting network (named after its developers, Ajtai, Komlós, and Szemerédi [8]) can sort *n* numbers in depth *O*(lg *n*) using *O*(*n* lg *n*) comparators. Unfortunately, the constants hidden by the *O*-notation are quite large (many, many thousands), and thus it cannot be considered practical.