Information Technology Reference
In-Depth Information
BM(2)
BM(2)
u
0
v
0
u
1
z
0
x
0
x
1
x
2
x
3
y
1
y
0
y
3
y
2
z
1
z
2
z
3
z
4
z
5
z
6
z
7
v
1
u
2
v
2
u
3
v
3
Figure 6.11
A recursive construction of the bitonic merging network
BM
(
4
)
. The even-
indexed elements of one sorted sequence are merged with the odd-indexed elements of the other,
the resulting sequences interleaved, and the even- and succeeding odd-indexed elements com-
pared. The inputs of one sequence are permuted to demonstrate that
BM
(
4
)
uses two copies of
BM
(
2
)
.
if
h
(
a
r
)
h
(
a
s
)
, the set of comparisons made by the sorting network will be exactly
thesameon
(
a
1
,
a
2
,
...
,
a
n
)
as on
(
h
(
a
1
)
,
h
(
a
2
)
,
...
,
h
(
a
n
))
.Thus,theoriginaloutput
(
b
1
,
b
2
,
...
,
b
n
)
will be replaced by the output sequence
(
h
(
b
1
)
,
h
(
b
2
)
,
...
,
h
(
b
n
))
.
Sinceitispresumedthatthecomparatornetworkputs
a
i
and
a
j
in the incorrect order,
let
h
(
x
)
be the following monotone function:
h
(
x
)=
0f
x
≤
a
i
1f
x>a
i
≤
Then the input and output sequences to the comparator network are binary. However,
the output sequence is not sorted (
a
j
appears before
a
i
but
h
(
a
j
)=
1and
h
(
a
i
)=
0),
contradicting the hypothesis of the theorem. It follows that all sequences over
A
must be
sorted correctly.
We now show that Batcher's bitonic merging circuit correctly merges two sorted lists. If
acorrect
m
-sorter exists, then a correct 2
m
-sorter can be constructed by combining two
m
-
sorters with a correct 2
m
-input bitonic merging circuit. It follows that a correct 2
m
-input
bitonic merging circuit exists if and only if the resulting sorting network is correct. This is
the core idea in a proof by induction of correctness of the 2
m
-input bitonic merging circuit.
The basis for induction is the fact that individual comparators correctly sort sequences of two
elements.
Suppose that
x
and
y
are sorted 0
−
1 sequences of length
m
.Let
x
have
k
0's and
m
−
k
1's, and let
y
have
l
0's and
m
−
l
1's. Then the leftmost merging network of Fig.
6.11
selects exactly
k/
2
0's from
x
and
l/
2
0's from
y
to produce the sequence
u
consisting of
a
=
k/
2
+
l/
2
0's followed by 1's. Similarly, the rightmost merging network produces
Search WWH ::
Custom Search