Site hosted by Build your free website today!
Ron's Site
Ramblings in mathematics and computer science

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:

  1. There is no known, practical method for creating n-item sorting networks with O(n*log(n)) comparators.
  2. 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.
  3. 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.