## Sorting algorithms## Sorting networks |

Definition: Let `J` = {0, ..., `n`-1} be an index set and let `A` be a set with an order relation . A data sequence is a mapping `a` : `J` `A`, i.e. a sequence of length `n` of data. The set of all data sequences of length `n` over `A` is denoted by `A`^{n}.

Definition: The sorting problem consists of reordering an arbitrary data sequence `a`_{0}, ..., `a`_{n-1,} `a`_{i} `A` to a data sequence `a`_{φ(0)}, ..., `a`_{φ(n-1)} such that

`a`_{φ(i)} `a`_{φ(j)} for `i` < `j`

where *φ* is a permutation of the index set `J` = {0, ..., `n`-1}.

This definition deals only with the simplest case of sorting a data sequence in ascending order. Later, when dealing with two-dimensional processor arrays, this definition has to be generalized by introducing an index set `J` = {0, ..., `n`-1}{0, ..., `n`-1} and a sorting direction ρ : `J` {0, ..., |`J`|-1}.

Comparator networks have been introduced informally in [Knu 73] for the case `J` = {0, ..., `n`-1}. A comparator [`i`:`j`] sorts the `i`th and the `j`th element of a data sequence into nondecreasing order. Formally, a comparator is a mapping applied to the data sequence:

Definition: A comparator is a mapping [`i`:`j`] : `A`^{n} `A`^{n}, `i`, `j` {0, ..., `n`-1} with

[`i`:`j`](`a`)_{i} = min(`a`_{i}, `a`_{j})

[`i`:`j`](`a`)_{j} = max(`a`_{i}, `a`_{j})

[`i`:`j`](`a`)_{k} = `a`_{k} for all `k` with `k``i`, `k``j`

for all `a` `A`^{n}.

Figure 1 shows the graphical representation of a comparator network with comparators [1:3] and [2:1], applied to the data sequence 6 8 5 1.

| |

Figure 1: Graphical representation of comparators | |

Definition: A comparator stage `S` is a composition of comparators

`S` = [`i`_{1}:`j`_{1}]· ...· [`i`_{k}:`j`_{k}] , `k`

such that all `i`_{r} and `j`_{s} are distinct (even the `i`_{r} and `j`_{s} among each other).

Comparators within a comparator stage can be executed in parallel.

Definition: A comparator network is a composition of comparator stages.

As an example, Figure 2 shows a comparator network with two stages.

| |

Figure 2: A comparator network with two stages | |

Definition: A sorting network is a comparator network that sorts all input sequences.

The comparator network of the example above is not a sorting network, since it does not sort the sequence 3 1 4 2.

The problem whether an arbitrary comparator network is a sorting network or not is not easy to solve in general. It is an NP-complete problem. Besides that, sorting networks can of course be constructed systematically and proved to be correct.

Sorting networks are special cases of general sorting algorithms, since all comparisons are data-independent.

An example of a sorting network is bubblesort:

| |

Figure 3: Sorting network bubblesort | |

The sorting network bubblesort consists of a first diagonal of `n`-1 comparators that move the greatest element to the last position. The remaining `n`-1 elements are sorted recursively by applying the same procedure. Bubblesort consists of `n`·(`n`-1)/2 comparators, arranged in 2`n` – 3 stages.

A similar sorting network is odd-even transposition sort. For sorting `n` input elements, `n`·(`n`-1)/2 comparators but only `n` comparator stages are required. Each stage consists of comparators [`i`: `i`+1] where `i` is odd or where `i` is even, in alternating order.

The main advantages of bubblesort and odd-even transposition sort are their simplicity and, important for hardware implementation, their locality and scalability. Locality means that comparators exist only between adjacent elements, scalability means that the structure does not change with size.

However, with an asymptotic complexitiy of Θ(`n`^{2}) comparators bubblesort and odd-even transposition sort are rather inefficient.

The lower bound for the sorting problem is Ω(`n` log(`n`)). This bound is tight even for sorting networks, as shown in [AKS 83]. However, due to its large constant, the AKS-network is impractical. But there are practical sorting networks with a complexity of `O`(`n`·log(`n`)^{2}) comparators: bitonic sort, odd-even mergesort and shellsort.

The following table summarizes the complexities of some sorting networks:

comparator stages | comparators | |||

Odd-even transposition sort | O(n) | O(n^{2}) | ||

Bubblesort | O(n) | O(n^{2}) | ||

Bitonic sort | O(log(n)^{2}) | O(n·log(n)^{2}) | ||

Odd-even mergesort | O(log(n)^{2}) | O(n·log(n)^{2}) | ||

Shellsort | O(log(n)^{2}) | O(n·log(n)^{2}) |

Whether an arbitrary comparator network `N` is a sorting network or not is independent of the input set `A`. It just depends on the structure of `N`. The 0-1-principle essentially states this fact.

Theorem: (0-1-principle)

A comparator network with `n` inputs that sorts all 2^{n} sequences of zeroes and ones is a sorting network (i.e. it sorts all sequences of arbitrary values, too).

The 0-1-principle is extremely useful for the proof of sorting networks.

[AKS 83] | M. Ajtai, J. Komlos, E. Szemeredi: An O(n log n) Sorting Network. Proceedings of the 25th ACM Symposium on Theory of Computing, 1-9 (1983) | |

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

Next: [0-1-principle] or |

H.W. Lang FH Flensburg lang@fh-flensburg.de Impressum © Created: 05.03.1997 Updated: 18.05.2010 |