Algebraic and Combinatorial Circuits - Models of Computation: Exploring the Power of Computing - page 271

A B C

a min( a , b )

b max( a , b )

(a)
Figure 6.10 (a) A comparison operator, and (b) an insertion-sorting network.

(b)

wavefront C. An insertion-sorting network can be realized with one comparator for the first
two inputs and k n .Let C insert ( n ) and D insert ( n )

denote the size and depth of an insertion-sorting network on n elements. Then C ( 2 )= 1and
D ( 2 )= 1, and

− 1 more for the k th input, 3 ≤ k ≤

C insert ( n ) ≤ C insert ( n − 1 )+ n − 1 = n ( n − 1 ) / 2

D insert ( n ) ≤ max( D insert ( n − 1 )+ 1, n − 1 )= n − 1

The depth bound follows because there is a path of length n 1 through the chain of compara-

tors added at the last wavefront and every path through the sorting network is extended by one
comparator with the addition of the new wavefront. A simple proof by induction establishes
these results.

−

6.8.1 Sorting Via Bitonic Merging
We now de s c r i be Batcher's bitonic merging network BM ( m ) , which is the basis for a sorting
network. Let x =( x 1 , x 2 , ... , x m ) and y =( y 1 , y 2 , ... , y m ) be ordered sequences of
length m .Thatis, x j ≤ y j + 1 . As suggested in Fig. 6.11 , the even-indexed

components of x are merged with the odd-indexed components of y , as are the odd-indexed
components of x and the even-indexed components of y . Each of the four lists that are merged
are themselves sorted. The two lists are interleaved and the k th and ( k + 1 ) st elements, k even,
are compared and swapped if necessary. To prove correctness of this circuit, we use the zero-one
principle which is stated below for sorting networks but applied later to merging networks.

x j + 1 and y j ≤

THEOREM 6.8.1 (Zero-one principle) Ifacomparatornetworkforinputsoveraset A correctly
sorts all binary inputs, it correctly sorts all inputs.
Proof The proof is by contradiction. Suppose the network correctly sorts all 0-1 sequences
but fails to sort the input sequence ( a 1 , a 2 , ... , a n ) . Then there are inputs a i and a j such
that a i <a j but the network puts a j before a i .
Since a sorting network contains only comparators, if we replace each entry a r in an
input sequence ( a 1 , a 2 , ... , a n ) with a new entry h ( a r ) ,where h ( a ) is monotonically
non-decreasing in a ( h ( a ) is non-decreasing as a increases), each comparison of entries
a r and a s is replaced by a comparison of entries h ( a r ) and h ( a s ) .Since a r <a s only