Sorting networksThe 01principle 
An indispensable tool for the proof of correctness of sorting networks is the 01principle [Knu 73]. The 01principle states the following:
Theorem: (01principle)
If a sorting network sorts every sequence of 0's and 1's, then it sorts every arbitrary sequence of values.
The proof of the 01principle is not very difficult. However, it is quite helpful to have some definitions and lemmas ready.
Definition: Let A and B be ordered sets. A mapping f : A B is called monotonic if for all a_{1}, a_{2} A
a_{1}a_{2} f(a_{1})f(a_{2})
Lemma: Let f : A B be a monotonic mapping. Then the following holds for all a_{1}, a_{2} A :
f(min(a_{1}, a_{2})) = min(f(a_{1}), f(a_{2}))
Proof: Let a_{1}a_{2} and thus f(a_{1})f(a_{2}). Then
min(a_{1}, a_{2}) = a_{1} and min(f(a_{1}), f(a_{2})) = f(a_{1})
This implies
f(min(a_{1}, a_{2})) = f(a_{1}) = min(f(a_{1}), f(a_{2}))
Similarly, if a_{2}a_{1} and therefore f(a_{2})f(a_{1}), we have
f(min(a_{1}, a_{2})) = f(a_{2}) = min(f(a_{1}), f(a_{2}))
An analogous property holds for the maxfunction.
Definition: Let f : A B be a mapping. The extension of f to finite sequences a = a_{0}, ..., a_{n1,} a_{i} A is defined as follows:
f(a_{0}, ..., a_{n1}) = f(a_{0}), ..., f(a_{n1}) , i.e.
f(a)_{i} = f(a_{i})
Lemma: Let f be a monotonic mapping and N a comparator network. Then N and f commutate, i.e. for every finite sequence a = a_{0}, ..., a_{n1} the following holds:
N( f(a) ) = f( N(a) )
In other words: a monotonic mapping f can be applied to the input sequence of comparator network N or to the output sequence, the result is the same.
Proof: For a single comparator [i:j] the following holds (see definition of comparator):
[i:j]( f(a) )_{i} = [i:j]( f(a_{0}), ..., f(a_{n1}) )_{i} = min( f(a_{i}), f(a_{j}) )
= f( min(a_{i}, a_{j}) ) = f( [i:j](a)_{i} ) = f( [i:j](a) )_{i}
This means that the ith element is the same regardless of the order of application of f and [i:j]. The same can be shown for the jth element and for all other elements. Therefore
[i:j]( f(a) ) = f( [i:j](a) )
For an arbitrary comparator network N (which is a composition of comparators) and a monotonic mapping f we have therefore
N( f(a) ) = f( N(a) )
Theorem: (01principle)
Let N be a comparator network. If every 01sequence is sorted by N, then every arbitrary sequence is sorted by N.
Proof: Suppose a with a_{i} A is an arbitrary sequence which is not sorted by N. This means N(a) = b is unsorted, i.e. there is a position k such that b_{k} > b_{k+1}.
Now define a mapping f : A {0, 1} as follows. For all c A let
f(c) = 

Obviously, f is monotonic. Moreover we have:
f(b_{k}) = 1 and f(b_{k+1}) = 0
i.e. f(b) = f(N(a)) is unsorted.
This means that N(f(a)) is unsorted or, in other words, that the 01sequence f(a) is not sorted by the comparator network N.
We have shown that, if there is an arbitrary sequence a that is not sorted by N, then there is a 01sequence f(a) that is not sorted by N.
Equivalently, if there is no 01sequence that is not sorted by N, then there can be no sequence a whatsoever that is not sorted by N.
Equivalently again, if all 01sequences are sorted by N, then all arbitrary sequences are sorted by N.
[Knu 73]  D.E. Knuth: The Art of Computer Programming, Vol. 3  Sorting and Searching. AddisonWesley (1973) 
H.W. Lang FH Flensburg lang@fhflensburg.de Impressum © Created: 02.02.1997 Updated: 24.02.2011 