{{Short description|Worst-case number of comparisons used by sorting algorithms}} In mathematics and computer science, the '''sorting numbers''' are a sequence of numbers introduced in 1950 by Hugo Steinhaus for the analysis of comparison sort algorithms. These numbers give the worst-case number of comparisons used by both binary insertion sort and merge sort. However, there are other algorithms that use fewer comparisons.
==Formula and examples== The <math>n</math>th sorting number is given by the formula{{r|fj}} {{bi|left=1.6|<math>\displaystyle n\lceil\log_2 n\rceil - 2^{\lceil\log_2 n\rceil} + 1.</math>}} The sequence of numbers given by this formula (starting with <math>n = 1</math>) is {{bi|left=1.6|0, 1, 3, 5, 8, 11, 14, 17, 21, 25, 29, 33, 37, 41, ... {{OEIS|A001855}}.}}
The same sequence of numbers can also be obtained from the recurrence relation{{r|as}}, :<math>A(n) = A\bigl(\lfloor n/2\rfloor\bigr) + A\bigl(\lceil n/2\rceil\bigr) + n - 1</math>.
It is an example of a 2-regular sequence.{{r|as}}
Asymptotically, the value of the <math>n</math>th sorting number fluctuates between approximately <math>n\log_2 n - n</math> and <math>n\log_2 n - 0.915n,</math> depending on the ratio between <math>n</math> and the nearest power of two.{{r|fj}}
==Application to sorting== In 1950, Hugo Steinhaus observed that these numbers count the number of comparisons used by binary insertion sort, and conjectured (incorrectly) that they give the minimum number of comparisons needed to sort <math>n</math> items using any comparison sort. The conjecture was disproved in 1959 by L. R. Ford Jr. and Selmer M. Johnson, who found a different sorting algorithm, the Ford–Johnson merge-insertion sort, using fewer comparisons.{{r|fj}}
The same sequence of sorting numbers also gives the worst-case number of comparisons used by merge sort to sort <math>n</math> items.{{r|as}}
==Other applications== The sorting numbers (shifted by one position) also give the sizes of the shortest possible superpatterns for the layered permutations.{{r|aepv}}
==References== <references> <ref name=aepv>{{citation | last1 = Albert | first1 = Michael | author1-link = Michael H. Albert | last2 = Engen | first2 = Michael | last3 = Pantone | first3 = Jay | last4 = Vatter | first4 = Vincent | issue = 3 | journal = Electronic Journal of Combinatorics | pages = P23:1–P23:5 | title = Universal layered permutations | volume = 25 | year = 2018| doi = 10.37236/7386 | s2cid = 52100342 | doi-access = free | arxiv = 1710.04240 }}</ref>
<ref name=as>{{citation | last1 = Allouche | first1 = Jean-Paul | last2 = Shallit | first2 = Jeffrey | author2-link = Jeffrey Shallit | doi = 10.1016/0304-3975(92)90001-V | issue = 2 | journal = Theoretical Computer Science | mr = 1166363 | pages = 163–197 | title = The ring of <math>k</math>-regular sequences | volume = 98 | year = 1992| doi-access = free }}. See Example 28, p. 192.</ref>
<ref name=fj>{{citation | last1 = Ford | first1 = Lester R. Jr. | author1-link = L. R. Ford Jr. | last2 = Johnson | first2 = Selmer M. | author2-link = Selmer M. Johnson | doi = 10.2307/2308750 | journal = American Mathematical Monthly | mr = 0103159 | pages = 387–389 | title = A tournament problem | volume = 66 | year = 1959| issue = 5 | jstor = 2308750 }}</ref> </references>
{{Classes of natural numbers}}
Category:Integer sequences Category:Comparison sorts