Sorting Networks and the END search algorithm


An oblivious comparison-based algorithm is such that the sequence of comparisons performed is the same for all inputs of any given size. This kind of algorithm has received much attention since it admits an implementation as circuits: comparison-swap can be hard-wired. Such an oblivious comparison-based algorithm for sorting n values is called an n-input sorting network (a survey of sorting network research is in [1]).

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:

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.

The Evolving Non-Determinism (END) search algorithm

The END algorithm can be seen as a massively parallel search algorithm for which elements of the population interact locally. Simulated evolution is used as the paradigm that focus the search in the state space.
This approach provided impressive results, in particular for the sorting network problem. Compared to Hillis' work, shorter sorting networks were discovered without any initial condition. Even a 25-year old result for the upper bound on the number of comparators for the 13-input case has been improved by one comparator!
The paper presenting the END algorithm can be downloaded by clicking here.
Some of these sorting networks discovered by END are presented below.



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