||This article includes a list of references, but its sources remain unclear because it has insufficient inline citations. (May 2014)|
A sorting network is an abstract mathematical model of a network of wires and comparator modules that is used to sort a sequence of numbers. Each comparator connects two wires and sorts the values by outputting the smaller value to one wire, and the larger to the other. The main difference between sorting networks and comparison sorting algorithms is that with a sorting network the sequence of comparisons is set in advance, regardless of the outcome of previous comparisons. This independence of comparison sequences is useful for parallel execution of the algorithms. Despite the simplicity of the model, sorting network theory is surprisingly deep and complex.
A sorting network consists of two items: comparators and wires. Each wire carries with it a value, and each comparator has two input wires, and two output wires. When two values enter a comparator, the comparator emits the lower value from the top wire, and the higher value from the bottom wire. A network of wires and comparators that will correctly sort all possible inputs into ascending order is called a sorting network.
The full operation of a simple sorting network is shown below. It is easy to see why this sorting network will correctly sort the inputs; note that the first four comparators will "sink" the largest value to the bottom and "float" the smallest value to the top. The final comparator simply sorts out the middle two wires.
Insertion and selection networks
We can easily construct a network of any size recursively using the principles of insertion and selection. Assuming we have a sorting network of size n, we can construct a network of size n + 1 by "inserting" an additional number into the already sorted subnet (using the principle behind insertion sort). We can also accomplish the same thing by first "selecting" the lowest value from the inputs and then sort the remaining values recursively (using the principle behind bubble sort).
The structure of these two sorting networks are very similar. A construction of the two different variants, which collapses together comparators that can be performed simultaneously shows that, in fact, they are identical.
The insertion network has a large depth of O(n) making it impractical. There are simple networks which achieve depth O((log n)2) (hence size O(n (log n)2)), such as Batcher odd–even mergesort, bitonic sort, Shell sort, and the Pairwise sorting network. These networks are often used in practice.
While it is easy to prove the validity of some sorting networks (like the insertion/bubble sorter), it is not always so easy. There are n! permutations of numbers in an n-wire network, and to test all of them would take a significant amount of time, especially when n is large. The number of test cases can be reduced significantly, to 2n, using the so-called zero-one principle. While still exponential, this is smaller than n! for all n >= 4, and the difference grows rapidly with increasing n.
The zero-one principle states that a sorting network is valid if it can sort all 2n sequences of 0s and 1s. This not only drastically cuts down on the number of tests needed to ascertain the validity of a network, it is of great use in creating many constructions of sorting networks as well. The principle has been proven by a special case of Bouricius's Theorem (Knuth, 1997) in 1954 by W. G. Bouricius.[clarification needed]
Complexity of testing sorting networks
It is unlikely that significant further improvements can be made for testing general sorting networks, unless P=NP, because the problem of testing whether a candidate network is a sorting network is known to be co-NP-complete.
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 asymptotically best known sorting network, called AKS network after its discoverers Ajtai, Komlós, and Szemerédi, achieves depth O(log n) and size O(n log n) for n inputs, which is asymptotically optimal. A simplified version of the AKS network was described by Paterson. While an important theoretical discovery, the AKS network has little or no practical application because of the large linear constants hidden by the Big-O notation. These are partly due to a construction of an expander graph. Finding sorting networks with size cn log n for small c remains a fundamental open problem.
Some important progress in designing optimal sorting network is done using genetic algorithm techniques as well. (M. Mitchell, 1998)
For 1 to 10 inputs optimal sorting networks are known. They have respectively 0, 1, 3, 5, 9, 12, 16, 19, 25 and 29 comparators (Knuth, 1997). The optimal depths for up to 16 inputs are known and are respectively 0, 1, 3, 3, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 9, 9.
- Parberry, Ian (1991). "On the Computational Complexity of Optimal Sorting Network Verification". PARLE '91: Parallel Architectures and Languages Europe, Volume I: Parallel Architectures and Algorithms, Eindhoven, The Netherlands, June 10–13, 1991, Proceedings: 252–269.
- Codish, Michael; Cruz-Filipe, Luís; Frank, Michael; Schneider-Kamp, Peter (2014). "Twenty-Five Comparators is Optimal when Sorting Nine Inputs (and Twenty-Nine for Ten)". arXiv:1405.5754 [cs.DM].
- Bundala, D.; Závodný, J. (2014). "Optimal Sorting Networks". Language and Automata Theory and Applications. Lecture Notes in Computer cience 8370. p. 236. arXiv:1310.6271. doi:10.1007/978-3-319-04921-2_19. ISBN 978-3-319-04920-5.
- O. Angel, A.E. Holroyd, D. Romik, B. Virag, Random Sorting Networks, Adv. in Math., 215(2):839–868, 2007.
- 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.
- Ajtai, M.; Komlós, J.; Szemerédi, E. (1983), "An O(n log n) sorting network", Proceedings of the 15th Annual ACM Symposium on Theory of Computing, pp. 1–9, doi:10.1145/800061.808726, ISBN 0-89791-099-0.
- M. S. Paterson, Improved sorting networks with O(log N) depth, Algorithmica 5 (1990), no. 1, pp. 75–92, doi:10.1007/BF01840378.
- M. Mitchell, An Introduction to Genetic Algorithms, The MIT Press, 1998. ISBN 0-262-63185-7. Chapter 1: Overview, pp. 21–27