A sorting network is a circuit with n input connections for data items to be presented in an arbitrary order, and n 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.

Examples of sorting algorithms that can be implemented as sorting networks are Bubble sort, Odd-even transposition sort , Odd-even merge sort , Bitonic sort , and Shellsort.

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.E. Batcher, Sorting networks and their applications, Proceedings of the AFIPS Spring Joint Computer Conference 32, 307--314 (1968)
• D.E. Knuth: The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison-Wesley (1973)

See also

• Batcher odd-even mergesort
• Sorting algorithm

External links

• Sorting Networks
• Sorting Networks
• Sorting networks and the END algorithm