Editing Sorting network (section)

==Constructing sorting networks==
Various algorithms exist to construct sorting networks of depth {{math|''O''(log<sup>2</sup> ''n'')}} (hence size {{math|''O''(''n'' log<sup>2</sup> ''n'')}}) such as [[Batcher odd–even mergesort]], [[bitonic sort]], [[Shell sort]], and the [[Pairwise sorting network]]. These networks are often used in practice.

It is also possible to construct networks of depth {{math|''O''(log ''n'')}} (hence size {{math|''O''(''n'' log ''n'')}}) using a construction called the ''AKS network'', after its discoverers [[Miklós Ajtai|Ajtai]], [[János Komlós (mathematician)|Komlós]], and [[Endre Szemerédi|Szemerédi]].<ref>{{Cite conference | doi = 10.1145/800061.808726| title = An {{math|O(n log n)}} sorting network| work = Proceedings of the fifteenth annual ACM symposium on Theory of computing | conference = [[Symposium on Theory of Computing|STOC]] '83| pages = 1–9| year = 1983| last1 = Ajtai | first1 = M. |author-link1 = Miklós Ajtai| last2 = Komlós | first2 = J. |author-link2 = János Komlós (mathematician)| last3 = Szemerédi | first3 = E. |author-link3 = Endre Szemerédi| isbn = 0-89791-099-0}}</ref> While an important theoretical discovery, the AKS network has very limited practical application because of the large linear constant hidden by the [[Big-O notation]].<ref name="clrs"/>{{rp|653}} These are partly due to a construction of an [[expander graph]].

A simplified version of the AKS network was described by [[Michael S. Paterson|Paterson]] in 1990, who noted that "the constants obtained for the depth bound still prevent the construction being of practical value".<ref>{{Cite journal | doi = 10.1007/BF01840378| title = Improved sorting networks with {{math|''O''(log ''N'')}} depth| journal = Algorithmica| volume = 5| issue = 1–4| pages = 75–92| year = 1990| last1 = Paterson | first1 = M. S.| s2cid = 2064561}}</ref>

A more recent construction called the ''zig-zag sorting network'' of size {{math|''O''(''n'' log ''n'')}} was discovered by [[Michael T. Goodrich|Goodrich]] in 2014.<ref>{{cite book|last1=Goodrich|first1=Michael|title=Proceedings of the forty-sixth annual ACM symposium on Theory of computing |chapter=Zig-zag sort |authorlink1=Michael T. Goodrich|arxiv=1403.2777|date=March 2014|doi=10.1145/2591796.2591830|pages=684–693|isbn=9781450327107|s2cid=947950}}</ref> While its size is much smaller than that of AKS networks, its depth {{math|''O''(''n'' log ''n'')}} makes it unsuitable for a parallel implementation.

===Optimal sorting networks===
For small, fixed numbers of inputs {{mvar|n}}, ''optimal'' sorting networks can be constructed, with either minimal depth (for maximally parallel execution) or minimal size (number of comparators). These networks can be used to increase the performance of larger sorting networks resulting from the [[divide and conquer algorithm|recursive]] constructions of, e.g., Batcher, by halting the recursion early and inserting optimal nets as base cases.<ref name="parberry91">{{cite journal |first=Ian |last=Parberry |title=A Computer Assisted Optimal Depth Lower Bound for Nine-Input Sorting Networks |journal=Mathematical Systems Theory |volume=24 |pages=101–116 |year=1991 |url=http://larc.unt.edu/ian/pubs/9-input.pdf |doi=10.1007/bf02090393|citeseerx=10.1.1.712.219 |s2cid=7077160 }}</ref> The following table summarizes the optimality results for small networks for which the optimal depth is known:

{| class="wikitable" style="text-align: center;"
|-
! style="text-align: left;" | {{mvar|n}}
| style="width: 20px;" | 1 || style="width: 20px;" | 2 || style="width: 20px;" | 3 || style="width: 20px;" | 4 || style="width: 20px;" | 5 || style="width: 20px;" | 6 || style="width: 20px;" | 7 || style="width: 20px;" | 8 || style="width: 20px;" | 9 || style="width: 20px;" | 10 || style="width: 20px;" | 11 || style="width: 20px;" | 12 || style="width: 20px;" | 13 || style="width: 20px;" | 14 || style="width: 20px;" | 15 || style="width: 20px;" | 16
|17
|- 
! style="text-align: left;" | Depth<ref name="codish_end_game">{{cite conference |last1=Codish |first1=Michael |last2=Cruz-Filipe |first2=Luís |last3=Ehlers |first3=Thorsten |last4=Müller |first4=Mike |last5= Schneider-Kamp |first5=Peter |title=Sorting Networks: to the End and Back Again |arxiv=1507.01428 |year=2015|bibcode=2015arXiv150701428C }}</ref>
| 0 || 1 || 3 || 3 || 5 || 5 || 6 || 6 || 7 || 7 || 8 || 8 || 9 || 9 || 9 || 9
|10
|- 
! style="text-align: left;" | Size, upper bound<ref name="codish"/>
| 0 || 1 || 3 || 5 || 9 || 12 || 16 || 19 || 25 || 29 || 35 || 39 || 45 || 51 || 56 || 60
|71
|- 
! style="text-align: left;" | Size, lower bound (if different)<ref name="vvoorhis">Obtained by Van Voorhis lemma and the value {{math|''S''(11) {{=}} 35}}</ref>
|  ||  ||  ||  ||  ||  ||  ||  ||  ||  ||  ||  || 43 || 47 || 51 || 55
|60
|}

For larger networks neither the optimal depth nor the optimal size are currently known. The bounds known so far are provided in the table below:

{| class="wikitable" style="text-align: center;"
|-
! style="text-align: left;" | {{mvar|n}}
| style="width: 30px;" | 18 || style="width: 30px;" | 19 || style="width: 30px;" | 20 || style="width: 30px;" | 21 || style="width: 30px;" | 22 || style="width: 30px;" | 23 || style="width: 30px;" | 24 || style="width: 30px;" | 25 || style="width: 30px;" | 26 || style="width: 30px;" | 27 || style="width: 30px;" | 28 || style="width: 30px;" | 29 || style="width: 30px;" | 30 || style="width: 30px;" | 31 || style="width: 30px;" | 32
|- 
! style="text-align: left;" | Depth, upper bound<ref name="codish_end_game"/><ref>{{cite journal |last1=Ehlers |first1=Thorsten |title=Merging almost sorted sequences yields a 24-sorter |journal=Information Processing Letters |date=February 2017 |volume=118 |pages=17–20 |doi=10.1016/j.ipl.2016.08.005}}</ref><ref name="sorterhunter">{{cite web |last1=Dobbelaere |first1=Bert |title=SorterHunter |url=https://github.com/bertdobbelaere/SorterHunter |website=GitHub |access-date=2 Jan 2022}}</ref>
| 11 || 11 || 11 || 12 || 12 || 12 || 12 || 13 || 13 || 14 || 14 || 14 || 14 || 14 
|14
|- 
! style="text-align: left;" | Depth, lower bound<ref name="codish_end_game"/>
| 10 || 10 || 10 || 10 || 10 || 10 || 10 || 10 || 10 || 10 || 10 || 10 || 10 || 10 
|10
|- 
! style="text-align: left;" | Size, upper bound<ref name="sorterhunter"/>
| 77 || 85 || 91 || 99 || 106 || 114 || 120 || 130 || 138 || 147 || 155 || 164 || 172 || 180 
|185
|- 
! style="text-align: left;" | Size, lower bound<ref name="vvoorhis"/>
| 65 || 70 || 75 || 80 || 85 || 90 || 95 || 100 || 105 || 110 || 115 || 120 || 125 || 130 
|135
|}

The first sixteen depth-optimal networks are listed in Knuth's ''[[The Art of Computer Programming|Art of Computer Programming]]'',<ref name="knuth">{{cite book |first=D. E. |last=Knuth |author-link=Donald Knuth |title=The Art of Computer Programming, Volume 3: Sorting and Searching |edition=Second |publisher=Addison–Wesley |year=1997 |isbn=978-0-201-89685-5 |pages=219–247|title-link=The Art of Computer Programming }} Section 5.3.4: Networks for Sorting.</ref> and have been since the 1973 edition; however, while the optimality of the first eight was established by [[Robert W. Floyd|Floyd]] and Knuth in the 1960s, this property wasn't proven for the final six until 2014<ref name="bundala_zavodny">{{Cite book| doi = 10.1007/978-3-319-04921-2_19| volume = 8370| pages = 236–247| series = Lecture Notes in Computer Science| year = 2014| last1 = Bundala | first1 = D. | last2 = Závodný | first2 = J. | title = Language and Automata Theory and Applications| chapter = Optimal Sorting Networks| isbn = 978-3-319-04920-5| arxiv = 1310.6271| s2cid = 16860013}}</ref> (the cases nine and ten having been decided in 1991<ref name="parberry91"/>).

For one to twelve inputs, minimal (i.e. size-optimal) sorting networks are known, and for higher values, lower bounds on their sizes {{math|''S''(''n'')}} can be derived inductively using a lemma due to Van Voorhis<ref name="knuth"/> (p.&nbsp;240): {{math|''S''(''n'') ≥ ''S''(''n'' − 1) + ⌈log<sub>2</sub>''n''⌉}}. The first ten optimal networks have been known since 1969, with the first eight again being known as optimal since the work of Floyd and Knuth, but optimality of the cases {{math|''n'' {{=}} 9}} and {{math|''n'' {{=}} 10}} took until 2014 to be resolved.<ref name="codish">{{cite conference |last1=Codish |first1=Michael |last2=Cruz-Filipe |first2=Luís |last3=Frank |first3=Michael |last4= Schneider-Kamp |first4=Peter |title=Twenty-Five Comparators is Optimal when Sorting Nine Inputs (and Twenty-Nine for Ten) |conference=Proc. Int'l Conf. Tools with AI (ICTAI) |arxiv=1405.5754 |year=2014 |pages=186–193|bibcode=2014arXiv1405.5754C }}</ref>
The optimality of the smallest known sorting networks for {{math|''n'' {{=}} 11}} and {{math|''n'' {{=}} 12}} was resolved in 2020.<ref name="harder">{{cite arXiv |eprint=2012.04400 |last1=Harder |first1=Jannis |title=An Answer to the Bose-Nelson Sorting Problem for 11 and 12 Channels |year=2020 |class=cs.DS }}</ref><ref name="knuth"/>

Some work in designing optimal sorting network has been done using [[genetic algorithm]]s: D. Knuth mentions that the ''smallest'' known sorting network for {{math|''n'' {{=}} 13}} was found by Hugues Juillé in 1995 "by simulating an evolutionary process of genetic breeding"<ref name="knuth"/> (p.&nbsp;226), and that the ''minimum depth'' sorting networks for {{math|''n'' {{=}} 9}} and {{math|''n'' {{=}} 11}} were found by Loren Schwiebert in 2001 "using genetic methods"<ref name="knuth"/> (p.&nbsp;229).

===Complexity of testing sorting networks===

Unless [[P vs NP|P=NP]], the problem of testing whether a candidate network is a sorting network is likely to remain difficult for networks of large sizes, due to the problem being [[co-NP]]-complete.<ref name=parberry>{{cite conference |last=Parberry|first=Ian|title=On the Computational Complexity of Optimal Sorting Network Verification|journal=Proc. PARLE '91: Parallel Architectures and Languages Europe, Volume I: Parallel Architectures and Algorithms, Eindhoven, the Netherlands |year=1991|pages=252–269}}</ref>