 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". 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.