|Ramblings in mathematics and computer science|
By Ron Zeno
Wednesday, July 10, 2002
A sorting network is a parallel sorting method that takes in a fixed number of items and sorts them by only applying compare-exchange operations.
For more information on sorting networks, see:
Sorting Networks and the END search algorithm by Hugues Juillé.
There are some very basic problems dealing with sorting networks that are unsolved:
- There is no known, practical method for creating n-item sorting networks with O(n*log(n)) comparators.
- The minimal delay-time to sort n items is unknown for n > 10. (The n = 9, 10 solution was found by exhaustive computer search via a supercomputer in the late 1980s. Solutions for larger n might be found using a distributed search.
- The minimal number of comparisons to sort n items is unknown for n > 8.
Knuth, D. "Sorting and Searching," The Art of Computer Programming, Vol. 3, 2nd ed., section 5.3.4.
Copyright © 2002 Ron Zeno
Diagram showing how a 4-input sorting network sorts the sequence 3, 1, 0, 2.I've created a reference of the best-known sorting networks for up to 16 inputs.