A quick introduction to sorting networks

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 from Prof. F. D. Lewis' Algorithm Design Essays Sorting Networks from Prof. H. W. Lang's Sequential and parallel sorting algorithms 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. References: 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.

Home