Sorting network
|
|
A sorting network is a circuit with n input connections for data items to be presented in an arbitrary order, and n output connections on which the items are to be output in sorted order. Inside the sorting network, the only elements used are comparators, which have two inputs and two outputs, and simply swap the input data items if they are in the wrong order.
Examples of sorting algorithms that can be implemented as sorting networks are Bubble sort, Odd-even transposition sort, Odd-even merge sort, Bitonic sort, and Shellsort.
In spite of the simple statement of the problem, sorting network theory is surprisingly deep and complex. Recent attempts at using genetic algorithms to optimise sorting networks have given results which have improved on decades of work by mathematicians and engineers.
The efficiency of a sorting network can be measured by its total size (the number of comparators used), or by its depth (the maximum number of comparators along any path from an input to an output). The best known sorting network, discovered by Ajtai, Komlós, and Szemerédi, achieves depth O(log n) and size O(n log n) for n inputs, which is optimal in both measures to within a constant factor; however, the constants are very large and for this reason the AKS sorting network is not used in practice.
References
- K.E. Batcher, Sorting networks and their applications, Proceedings of the AFIPS Spring Joint Computer Conference 32, 307--314 (1968)
- D.E. Knuth: The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison-Wesley (1973)
- M. Ajtai, J. Komlós, and E. Szemerédi. An O(n log n) sorting network. Combinatorica 3(1), 1-19, 1983.
See also
External links
- Sorting Networks (http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/sortieren.htm)
- Sorting Networks (http://cs.engr.uky.edu/~lewis/essays/algorithms/sortnets/sort-net.html)
- Sorting networks and the END algorithm (http://www.cs.brandeis.edu/~hugues/sorting_networks.html)