Sorting network
From Wikipedia, the free encyclopedia
A sorting network is an abstract model of a network of wires and comparator modules that is used to sort a sequence of numbers. Each comparator connects two wires and sort the values by outputting the smaller value to one wire, and a larger value to the other. The main difference between sorting networks and comparison sorting algorithms is that the sequence of comparisons is set in advance, regardless of the outcome of previous comparisons.
A physical sorting network can be implemented in hardware for any fixed number of elements. It operates in time proportional to the network's depth; by exploiting massive parallelism, such a device allows sorting exponentially more quickly than a sorting algorithm running on a conventional microprocessor. Examples of serial 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. The constants implied by the "O" notation are very large, in part due to the fact that such network needs a good explicit construction of an expander graph. For this reason the AKS sorting network is not used in practice.
[edit] References
- K.E. Batcher, Sorting networks and their applications, Proceedings of the AFIPS Spring Joint Computer Conference 32, 307--314 (1968)
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 1990. ISBN 0-262-03293-7. Chapter 27: Sorting Networks, pp.704–724.
- D.E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 5.3.4: Networks for Sorting, pp. 219–247.
- M. Ajtai, J. Komlós, and E. Szemerédi. An O(n log n) sorting network. Combinatorica 3(1), 1-19, 1983.
