Sorting networks

Odd-even transposition sort

 German version  up

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.

Figure 1: Sorting network odd-even transposition sort for n = 8
Figure 1: Sorting network odd-even transposition sort for n = 8

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 = a0, ..., an-1 be a 0-1-sequence.

Case 1: If an-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 a0, ..., an-2 of length n-1. Since element an-1 is already at its proper position the whole sequence a is sorted. The following figure illustrates this case.

Obsolete comparators in case 1 Resulting sorting network for n-1 elements
Figure 2: Case 1

Case 2: If an-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 a0, ..., an-2. The network is crossed by a line that moves an-1 = 0 to its proper position. Therefore, the whole sequence a is sorted. In the following figure this case is shown.

Situation in case 2
Figure 3: Case 2

This proves the proposition for arbitrary n element natural numbers.

References

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

 

Next:   [Odd-even mergesort]   or   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 10.03.1997   Updated: 04.06.2016
Valid HTML 4.01 Transitional