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.


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)  =   open brace
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.


[Knu 73]   D.E. Knuth: The Art of Computer Programming, Vol. 3 - Sorting and Searching. Addison-Wesley (1973)




H.W. Lang   Impressum   Datenschutz
Created: 02.02.1997   Updated: 07.02.2023