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

A reference of the best-known sorting networks for up to 16 inputs.

By Ron Zeno
Saturday, May 11, 2002

The diagram belows shows the optimal sorting networks for n = 2 through 13 and n = 16.  For n = 10 and 12, both comparison-optimal and delay optimal networks are shown. For n = 13, a variation of one of Hughes 45-comparator networks is shown. The networks for n >= 8 are examples of structurally equivalent networks to those found in Knuth. The optimal sorting networks not shown for n = 13, 14 and 15 can be trivially constructed from the 16-sorters by removing outer vertical "wires".

Image of optimal sorting networks for n <= 16

 

Number of comparisons in comparison-optimal networks versus other sorting methods.
Inputs  1  2  3  4  5 6 7 8 9 10 11 12 13 14 15 16
Delay 0 1 3 3 5 5 6 6 7 8 8 9 10 10 10 10
Comparisons 0 1 3 5 9 12 16 19 25 29 35 39 45 51 56 60
Batcher's 0 1 3 5 9 12 16 19 26 31 37 41 48 53 59 63
Mergesort 0 1 3 5 7 10 13 16 19 22 26 30 34 38 42 46
Optimal sort 0 1 3 5 7 10 13 16 19 22 26 30 >32 >36 >40 >44

The networks for n <= 8 have been proven to be the best possible.  Additionally, it has been proven that a delay of 7 stages is minimal for n = 9 and 10.  The minimum number of comparisons for a sorting network is known to be O(n*log(n)), but the best-known and practical methods for creating sorting networks produce networks with O(n*log(n)^2) comparisons.

 

What do I mean by "structurally equivalent" sorting networks?

Two sorting networks A and B are structurally equivalent if for each delay level there are the same number of comparitors at that level in network A as there are in network B and these sets of comparitors do the same amount of work in partially sorting the possible inputs.

For example, there are literally over a million 10-sorters structurally equivalent to the 29-comparator one in the diagram above.  Consider:

  1. Any set of 5 disjoint pairs works for the first 5 comparators (945 possibilities),
  2. Any 8 of the 10 elements can be used for the next 4 comparators (45 possibilities, and there are 3 or so arrangements of the 8 chosen that will work),
  3. After that, there are at least 8 variations of the remaining network = 945*45*3*8 = 1,020,600.

Since there are about 9,495^8 different 10-input networks of delay 8, that makes the chance of randomly finding one to be about 1 in 6.6 * 10^26. 

 

References:

Knuth, D. "Sorting and Searching," The Art of Computer Programming, Vol. 3, 2nd ed., section 5.3.4.

Copyright 2002 Ron Zeno

For an introduction to sorting networks, see my quick introduction.

Sorting networks can be comparison-optimal, delay-optimal, or both.  Comparison-optimal networks have the minimum (known) number of compare-exchange operations.  Delay-optimal networks have the minimum (known) number of sets of compare-exchange operations that can be applied in parallel.

Networks that are both comparison- and delay-optimal are rare.  They exist for n <= 9 and n = 11, thus this diagram contains two networks each for n = 10, 12, and 16.

The networks not included in the diagram are the 47-comparison, delay-9 13-sorter; the 52-comparison, delay-9 14-sorter; the 51-comparison, delay-10 14-sorter; the 57-comparison, delay-9 15-sorter; and the 56-comparison, delay-10 15-sorter.

Home