## Sorting networks## Odd-even transposition sort |

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

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

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`_{0}, ..., `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`_{0}, ..., `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`_{0}, ..., `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` .

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

Next: [Odd-even mergesort] or |

H.W. Lang Hochschule Flensburg lang@hs-flensburg.de Impressum © Created: 10.03.1997 Updated: 04.06.2016 |