Editing Sorting network (section)

{{Short description|Abstract devices built up of a fixed number of "wires"}}
[[File:SimpleSortingNetwork2.svg|thumb|300px|A simple sorting network consisting of four wires and five connectors]]

In [[computer science]], '''comparator networks''' are abstract devices built up of a fixed number of "wires", carrying values, and comparator modules that connect pairs of wires, swapping the values on the wires if they are not in a desired order. Such networks are typically designed to perform [[sorting algorithm|sorting]] on fixed numbers of values, in which case they are called '''sorting networks'''.

Sorting networks differ from general [[comparison sort]]s in that they are not capable of handling arbitrarily large inputs, and in that their sequence of comparisons is set in advance, regardless of the outcome of previous comparisons. In order to sort larger amounts of inputs, new sorting networks must be constructed. This independence of comparison sequences is useful for parallel execution and for implementation in [[computer hardware|hardware]]. Despite the simplicity of sorting nets, their theory is surprisingly deep and complex. Sorting networks were first studied circa 1954 by Armstrong, Nelson and O'Connor,<ref name="knuth"/> who subsequently patented the idea.<ref>{{cite patent |country=US |number=3029413 |title=Sorting system with {{mvar|n}}-line sorting switch |pubdate=10 April 1962 |fdate= 21 February 1957 |inventor1-first=Daniel G. |inventor1-last=O'Connor |inventor2-first=Raymond J. |inventor2-last=Nelson}}</ref>

Sorting networks can be implemented either in [[computer hardware|hardware]] or in [[software]]. [[Donald Knuth]] describes how the comparators for binary integers can be implemented as simple, three-state electronic devices.<ref name="knuth"/> [[Ken Batcher|Batcher]], in 1968, suggested using them to construct [[switch|switching networks]] for computer hardware, replacing both [[Bus (computing)|buses]] and the faster, but more expensive, [[crossbar switch]]es.<ref>{{cite conference |first=K. E. |last=Batcher |url=http://www.cs.kent.edu/~batcher/sort.ps |title=Sorting networks and their applications |conference=Proc. AFIPS Spring Joint Computer Conference |pages=307–314 |year=1968}}</ref> Since the 2000s, sorting nets (especially [[bitonic sorter|bitonic mergesort]]) are used by the [[General-purpose computing on graphics processing units|GPGPU]] community for constructing sorting algorithms to run on [[graphics processing unit]]s.<ref>{{Cite journal | doi = 10.1109/JPROC.2008.917757| title = GPU Computing| journal = Proceedings of the IEEE| volume = 96| issue = 5| pages = 879–899| year = 2008| last1 = Owens | first1 = J. D. | last2 = Houston | first2 = M.| last3 = Luebke | first3 = D.| last4 = Green | first4 = S.| last5 = Stone | first5 = J. E. | last6 = Phillips | first6 = J. C. | s2cid = 17091128}}</ref>