Sorting networks

An elementary sorting network is odd-even transposition sort [Knu 73]. It is widely used for sorting on two-dimensional processor arrays.

Sorting network

The network odd-even transposition sort for n input data consists of n comparator stages. In each stage, either all inputs at odd index positions or all inputs at even index positions are compared with their neighbours. Odd and even stages alternate (Figure 1). The number of comparators is n·(n-1)/2.

Proof of correctness

It is shown that every sequence of zeroes and ones is sorted by Odd-even transposition sort. Then, by the 0-1-principle, every sequence of arbitrary elements will be sorted. The proof proceeds by induction on the problem size n.

Proposition: The odd-even transposition comparator network for n elements sorts every 0-1-sequence of length n.

Induction base: n = 1
The odd-even transposition comparator network for one element consists of just a straight line with 0 comparators. Since every 0-1-sequence of length 1 is sorted the proposition is true for n = 1.

Induction hypothesis: Let the proposition be true for n-1.

Induction conclusion:
Let N be an odd-even transposition comparator network for n > 1 elements and let a = a₀, ..., a_n-1 be a 0-1-sequence.

Case 1: If a_n-1 = 1, then the comparators [n-2:n-1] are obsolete. An odd-even transposition comparator network for n-1 elements remains (plus a superfluous comparator stage). By induction hypothesis, this network sorts the sequence a₀, ..., a_n-2 of length n-1. Since element a_n-1 is already at its proper position the whole sequence a is sorted. The following figure illustrates this case.

Figure 2: Case 1

Case 2: If a_n-1 = 0, then all comparators encountered by this zero perform an exchange (even if no exchange is necessary when the other element is also a zero, the result is the same). The corresponding comparators can be replaced by crossing lines. An odd-even transposition comparator network for n-1 elements remains which sorts, by induction hypothesis, the sequence a₀, ..., a_n-2. The network is crossed by a line that moves a_n-1 = 0 to its proper position. Therefore, the whole sequence a is sorted. In the following figure this case is shown.

Figure 3: Case 2

This proves the proposition for arbitrary n ∈ ℕ.

References

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