# Sorting number

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Sorting_number
> Markdown URL: https://mediated.wiki/source/Sorting_number.md
> Source: https://en.wikipedia.org/wiki/Sorting_number
> Source revision: 1328064441
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Worst-case number of comparisons used by sorting algorithms}}
In [mathematics](/source/mathematics) and [computer science](/source/computer_science), the '''sorting numbers''' are a sequence of numbers introduced in 1950 by [Hugo Steinhaus](/source/Hugo_Steinhaus) for the analysis of [comparison sort](/source/comparison_sort) algorithms. These numbers give the [worst-case](/source/Worst-case_complexity) number of comparisons used by both [binary insertion sort](/source/insertion_sort) and [merge sort](/source/merge_sort). However, there are other [algorithms](/source/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](/source/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](/source/k-regular_sequence).{{r|as}}

[Asymptotically](/source/Asymptotic_analysis), 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](/source/power_of_two).{{r|fj}}

==Application to sorting==
In 1950, [Hugo Steinhaus](/source/Hugo_Steinhaus) observed that these numbers count the number of comparisons used by [binary insertion sort](/source/insertion_sort), and conjectured (incorrectly) that they give the minimum number of comparisons needed to sort <math>n</math> items using any [comparison sort](/source/comparison_sort). The conjecture was disproved in 1959 by [L. R. Ford Jr.](/source/L._R._Ford_Jr.) and [Selmer M. Johnson](/source/Selmer_M._Johnson), who found a different sorting algorithm, the Ford–Johnson [merge-insertion sort](/source/merge-insertion_sort), using fewer comparisons.{{r|fj}}

The same sequence of sorting numbers also gives the [worst-case](/source/Worst-case_complexity) number of comparisons used by [merge sort](/source/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 [superpattern](/source/superpattern)s for the [layered permutation](/source/layered_permutation)s.{{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](/source/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](/source/Theoretical_Computer_Science_(journal))
 | 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](/source/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

---
Adapted from the Wikipedia article [Sorting number](https://en.wikipedia.org/wiki/Sorting_number) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Sorting_number?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.