Sorting network
A sorting network is an idealized circuit with a number of input connections for data items to be presented in an arbitrary order, and a number of output connections on which the items are to be output in sorted order. Inside the sorting network, the only elements used are comparators, which have two inputs and two outputs, and simply swap the input data items if they are in the wrong order, and connections between these comparators.
In spite of the simple statement of the problem, sorting network theory is surprisingly deep and complex. Recent attempts at using genetic algorithms to optimise sorting networks have given results which have improved on decades of work by mathematicians and engineers.
References
- K. Batcher, Sorting networks and their applications, Proceedings of the AFIPS Spring Joint Computer Conference 32, Reston, VA, 1968, pp. 307--314
See also
