SKEDSOFT

The zero-one principle

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.

The proof of the zero-one principle relies on the notion of a monotonically increasing function.

If a comparison network transforms the input sequence a = 〈a₁, a₂,...,a_n〉 into the output sequence b = 〈b₁, b₂,...,b_n〉, then for any monotonically increasing function f, the network transforms the input sequence f (a) = 〈f(a₁), f(a₂),...,f(a_n)〉 into the output sequence f(b) = 〈f(b₁), f(b₂),...,f(b_n)〉.

Proof We shall first prove the claim that if f is a monotonically increasing function, then a single comparator with inputs f(x) and f(y) produces outputs f(min(x, y)) and f(max(x, y)). We then use induction to prove the lemma.

To prove the claim, consider a comparator whose input values are x and y. The upper output of the comparator is min(x, y) and the lower output is max(x, y). Suppose we now apply f(x) and f(y) to the inputs of the comparator, as is shown in Figure 27.4. The operation of the comparator yields the value min(f(x), f(y)) on the upper output and the value max(f(x), f(y)) on the lower output. Since f is monotonically increasing, x ≤ y implies f(x) ≤ f(y). Consequently, we have the identities

Thus, the comparator produces the values f(min(x, y)) and f(max(x, y)) when f(x) and f(y) are its inputs, which completes the proof of the claim.

We can use induction on the depth of each wire in a general comparison network to prove a stronger result than the statement of the lemma: if a wire assumes the value a_i when the input sequence a is applied to the network, then it assumes the value f(a_i) when the input sequence f(a) is applied. Because the output wires are included in this statement, proving it will prove the lemma.

For the basis, consider a wire at depth 0, that is, an input wire a_i. The result follows trivially: when f(a) is applied to the network, the input wire carries f(a_i). For the inductive step, consider a wire at depth d, where d ≥ 1. The wire is the output of a comparator at depth d, and the input wires to this comparator are at a depth strictly less than d. By the inductive hypothesis, therefore, if the input wires to the comparator carry values a_i and a_j when the input sequence a is applied, then they carry f(a_i) and f(a_j) when the input sequence f(a) is applied. By our earlier claim, the output wires of this comparator then carry f(min(a_i, a_j)) and f(max(a_i, a_j)). Since they carry min(a_i, a_j) and max(a_i, a_j) when the input sequence is a, the lemma is proved.

As an example of the application of Lemma 27.1, Figure 27.5(b) shows the sorting network from Figure 27.2 (repeated in Figure 27.5(a)) with the monotonically increasing function f(x) = ⌈x/2⌉ applied to the inputs. The value on every wire is f applied to the value on the same wire in Figure 27.2.

Figure 27.5: (a) The sorting network from Figure 27.2 with input sequence 〈9, 5, 2, 6〉. (b) The same sorting network with the monotonically increasing function f(x) = f(⌈x/2⌉) applied to the inputs. Each wire in this network has the value of f applied to the value on the corresponding wire in (a).

When a comparison network is a sorting network, Lemma 27.1 allows us to prove the following remarkable result.