32 Rolf Wanka
In what follows we present a sketch of its proof emphasizing the idea. For
the proof of correctness of the Bitonic Sorter, we only need the statement of
the 0-1 principle, not its proof. Therefore during first reading, the reader may
skip the following short text and resume reading at (∗∗).
The idea of the proof of the 0-1 principle is quite simple. In order to
illustrate it, we show instead of the 0-1 principle the 0-1-2-3-4 principle. Here,
in the above statement we replace “only of 0s and 1s” with “only of 0s, 1s,
2s, 3s, and 4s.”
Now let C
n
be an arbitrary, but fixed comparator circuit with n wires. Con-
sider an arbitrary sequence a =(a[1],...,a[n]) of the numbers 1 through n.
Every number appears exactly once. Such a sequence is called a permutation.
Let a be the input to C
n
. We pick two different keys i and j, i<j,froma
and construct the sequence b =(b[1],...,b[n]) with
b[k]=
⎧
⎪
⎪
⎪
⎪
⎪
⎪
⎨
⎪
⎪
⎪
⎪
⎪
⎪
⎩
0ifa[k] <i
1ifa[k]=i
2ifi<a[k] <j
3ifa[k]=j
4ifj<a[i].
That means that in b, all keys less that i are mapped to 0, i is mapped to 1,
all keys between i and j are mapped to 2, j is mapped to 3, and all keys
greater than j are mapped to 4. For example, a =(6, 1, 5, 2, 3, 4, 7) with i =3
and j = 5 is transformed to b =(4, 0, 3, 0, 1, 2, 4).
No
w, a and b are fed
into C
n
.MarkinC
n
the paths of i and j on their
way from left to right in red and blue, respectively. Then compare the red
and blue paths to the paths of 1 and 3 when b is input to the circuit. We see
that 1 takes the red path, and that 3 takes the blue path! Why? If we only
have a single comparator (although n is arbitrary), this is obviously true. And
an arbitrary comparator circuit can be considered a successive application of
single comparators. So it is true for any circuit. Hence, i from a will be output
on the same wire as 1 from b,andj from a will be output on the same wire
as 3 from b.
Now suppose that there is a sequence a that is not sorted by C
n
.Then
there are two keys i and j, i<j, that are output in wrong order. So, the
corresponding sequence b is also not sorted. This means the other way around
that, if all 0-1-2-3-4 sequences are sorted by C
n
, there can be no permutation
which is not sorted by C
n
.
Now it is just a small step to the 0-1 principle: In the construction of b,
replace the keys 0, 1, and 2 with 0, and 3 and 4 with 1. Call this sequence c.
In our example, this yields c =(1, 0, 1, 0, 0, 0, 1). A close look reveals that on
the same wire where i from a is output, a 0 from c is output. Analogously,
where j from a is output, a 1 from c is output. And it is easy to see that all
arguments for b and c also hold if a is not a permutation. So we may repeat
the argument: For every input sequence a that is not sorted, there is a 0-1