There is a convenient graphical representation of sorting networks.
An horizontal line represents each input of the sorting network and
a connection between two lines represents each comparator which
compares the two elements and exchanges them if the one on the upper line is
larger than the one on the lower line.
The input of the sorting network is on the left of the representation.
Elements at the output are sorted and the largest element migrates to the
bottom line.
Performance of a sorting network can be measured in two different ways:
Nb inputs | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
Upper bound | 0 | 1 | 3 | 3 | 5 | 5 | 6 | 6 | 7 | 7 | 8 | 8 | 9 | 9 | 9 | 9 |
Lower bound | 0 | 1 | 3 | 3 | 5 | 5 | 6 | 6 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 |
Nb inputs | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
Comparators | 0 | 1 | 3 | 5 | 9 | 12 | 16 | 19 | 25 | 29 | 35 | 39 | 51 | 56 | 60 |
The 16-input sorting network has been the most challenging one. Knuth [1] recounts its history as follows. First, in 1962, Bose and Nelson discovered a method for constructing sorting networks that used 65 comparisons and conjectured that it was best possible. Two years later, Floyd and Knuth, and independently Batcher, found a new method and designed a sorting network using 63 comparisons. Then, a 62-comparator sorting network was found by Shapiro in 1969, soon to be followed by Green's 60 comparator network, presented below.
Until recently, none of the upper bounds presented in [1] has been
improved, neither Green's optimal construction for a 16-input sorting network
has been reproduced!
A famous work after Hillis [2], addressed the problem of finding optimal sorting networks (regarding the number of comparators) in the case of 16 inputs. Hillis used a simulated evolution approach and got impressive results, given the difficulty of the problem. Moreover, his work addressed some innovative issues for search algorithms, like the use of co-evolution. However, he hasn't been able to achieve the best known upper bound and discovered only a 61-comparator solution, presented below.
Moreover, Hillis introduced an important bias in his search algorithm by initializing the population with the first 32 comparators of the best known construction. The search was limited around this local optimum and, thus, the final solution still used these initial 32 comparators.
[1] Knuth, D. E. (1973). The Art of Computer Programming, volume 3:
Sorting and Searching. Addison Wesley.
[2] Hillis, W. D. (1992). Co-evolving parasites improve simulated evolution
as an optimization procedure. In Langton, C. et al. (Eds.),
Artificial Life II. Addison Wesley.