| Ron's Site |
| Ramblings in mathematics and computer science |
By Ron Zeno
Saturday, May 11, 2002The 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".
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:
- Any set of 5 disjoint pairs works for the first 5 comparators (945 possibilities),
- 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),
- 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.
