Sorting networks

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.

Definition:  Let A and B be ordered sets. A mapping f : A → B is called monotonic if for all a₁, a₂ ∈ A

a₁ ≤ a₂   ⇒   f(a₁) ≤ f(a₂)

Lemma:  Let f : A → B be a monotonic mapping. Then the following holds for all a₁, a₂ ∈ A :

f(min(a₁, a₂))  =  min(f(a₁), f(a₂))

Proof:  Let a₁ ≤ a₂ and thus f(a₁) ≤ f(a₂). Then

min(a₁, a₂) = a₁   and   min(f(a₁), f(a₂)) = f(a₁)

This implies

f(min(a₁, a₂))  =  f(a₁)  =  min(f(a₁), f(a₂))

Similarly, if a₂ ≤ a₁ and therefore f(a₂) ≤ f(a₁), we have

f(min(a₁, a₂))  =  f(a₂)  =  min(f(a₁), f(a₂))

Definition:  Let f : A → B be a mapping. The extension of f to finite sequences a = a₀, ..., a_n-1,  a_i ∈ A is defined as follows:

f(a₀, ..., a_n-1)  =  f(a₀), ..., f(a_n-1) ,   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₀, ..., a_n-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(a₀), ..., f(a_n-1))_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:  (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 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

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 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.