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

the sequence v consisting of b =

k/ 2 l/ 2 x − x

+ 0's followed by 1's. Since is 0 or

1, it follows that either a = b , a = b 1, or a = b + 1. Thus, when u and v are interleaved

to produce the sequence z it contains a sequence of a + b 0's followed by 1's when a = b or
a = b + 1, or 2 a 0's followed by 1 0 followed by 1's when a = b

−

−

1, as suggested below:

2 a
0, 0, ... ,0,1,0,1, ... ,1

z =

1 the outputs in positions 2 k and 2 k + 1 are compared and
swapped, if necessary, the output will be properly sorted.
The graph of BM ( 4 ) of Fig. 6.11 illustrates that BM ( 4 ) is constructed of two copies of
BM ( 2 ) . In addition, it demonstrates that the operations of each of the two BM ( 2 ) subnet-
works can be performed in parallel. Another important observation is that this graph is iso-
morphic to an FFT graph when the comparators are replaced by two-input butterfly graphs,
as shown in Fig. 6.12 .
THEOREM 6.8.2 Batcher's 2 n -input bitonic merging circuit BM ( n ) for merging two sorted n -
sequences, n = 2 k , has the following size and depth bounds over the basis Ω of comparators:
C Ω ( BM ( n ))

≤ k ≤ m −

Thus, if for each 0

≤ n (log n + 1 )

log n + 1
Proof Let C ( k ) and D ( k ) be the size and depth of BM ( n ) .Then C ( 0 )= 1, D ( 0 )= 1,
C ( k )= 2 C ( k

D Ω ( BM ( n )) ≤

1 )+ 2 k ,and D ( k )= D ( k 1 )+ 1. It follows that C ( k )=( k + 1 ) 2 k

− −

and D ( k )= k + 1. (See Problem 6.29 .)

This leads us to the recursive construction of a Batcher's bitonic sorting network BS ( n )
for sequences of length n , n = 2 k . It merges the output of two copies of BS ( n/ 2 ) using
acopyofBatcher's n -input bitonic merging circuit BM ( n/ 2 ) . The proof of the following
theorem is left as an exercise. (See Problem 6.28 .)
THEOREM 6.8.3 Batcher's n -input bitonic sorting circuit BS ( n ) for n = 2 k has the following
size and depth bounds over the basis Ω of comparators:
C Ω ( BS ( n )) = n

4 [log 2 n +log n ]

x 0 z 0

y 3
x 2
y 1
x 1
y 2
x 3
y 0

z 4
z 2
z 6
z 1
z 5
z 3
z 7

Figure 6.12 The graph resulting from the replacement of comparators in Fig. 6.11 with two-
input butterfly graphs and the permutation of inputs. All edges are directed from left to right.