# Sorting networks

## The 0-1-principle  An indispensable tool for the proof of correctness of sorting networks is the 0-1-principle [Knu 73]. The 0-1-principle states the following:

Theorem:  (0-1-principle)

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 0-1-principle is not very difficult. However, it is quite helpful to have some definitions and lemmas ready.

### Preliminaries

Definition:  Let A and B be ordered sets. A mapping f : A B is called monotonic if for all a1, a2 A

a1 a2 f(a1) f(a2)

Lemma:  Let f : A B be a monotonic mapping. Then the following holds for all a1, a2 A :

f(min(a1, a2))  =  min(f(a1), f(a2))

Proof:  Let a1 a2 and thus f(a1) f(a2). Then

min(a1, a2) = a1   and   min(f(a1), f(a2)) = f(a1)

This implies

f(min(a1, a2))  =  f(a1)  =  min(f(a1), f(a2))

Similarly, if a2 a1 and therefore f(a2) f(a1), we have

f(min(a1, a2))  =  f(a2)  =  min(f(a1), f(a2))

An analogous property holds for the max-function.

Definition:  Let f : A B be a mapping. The extension of f to finite sequences a = a0, ..., an-1,  ai A is defined as follows:

f(a0, ..., an-1)  =  f(a0), ..., f(an-1) ,   i.e.

f(a)i  =  f(ai)

Lemma:  Let f be a monotonic mapping and N a comparator network. Then N and f commutate, i.e. for every finite sequence a = a0, ..., an-1 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(a0), ..., f(an-1) )i  =  min( f(ai), f(aj) )

=  f( min(ai, aj) )  =  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) )

### Proof of the 0-1-principle

Theorem:  (0-1-principle)

Let N be a comparator network. If every 0-1-sequence is sorted by N, then every arbitrary sequence is sorted by N.

Proof:  Suppose a with ai 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 bk > bk+1.

Now define a mapping f : A {0, 1} as follows. For all c A let

f(c)  = 0 if  c < bk 1 if  c bk

Obviously, f is monotonic. Moreover we have:

f(bk) = 1   and   f(bk+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 0-1-sequence 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 0-1-sequence f(a) that is not sorted by N.

Equivalently, if there is no 0-1-sequence that is not sorted by N, then there can be no sequence a whatsoever that is not sorted by N.

Equivalently again, if all 0-1-sequences are sorted by N, then all arbitrary sequences are sorted by N.

### References

 [Knu 73] D.E. Knuth: The Art of Computer Programming, Vol. 3 - Sorting and Searching. Addison-Wesley (1973)  H.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 02.02.1997   Updated: 04.06.2018 