Inmathematics andcomputer science, thesorting numbers are a sequence of numbers introduced in 1950 byHugo Steinhaus for the analysis ofcomparison sort algorithms. These numbers give theworst-case number of comparisons used by bothbinary insertion sort andmerge sort. However, there are otheralgorithms that use fewer comparisons.

The${\displaystyle n}$th sorting number is given by the formula^[1]

${\displaystyle {\displaystyle n\lceil {\log }_{2}n\rceil -2^{\lceil {\log }_{2}n\rceil }+1.}}$

The sequence of numbers given by this formula (starting with${\displaystyle n=1}$) is

The same sequence of numbers can also be obtained from therecurrence relation^[2],

${\displaystyle A(n)=A(\lfloor n/2\rfloor )+A(\lceil n/2\rceil )+n-1}$.

It is an example of a2-regular sequence.^[2]

Asymptotically, the value of the${\displaystyle n}$th sorting number fluctuates between approximately${\displaystyle n{\log }_{2}n-n}$ and${\displaystyle n{\log }_{2}n-0.915n,}$ depending on the ratio between${\displaystyle n}$ and the nearestpower of two.^[1]

In 1950,Hugo Steinhaus observed that these numbers count the number of comparisons used bybinary insertion sort, and conjectured (incorrectly) that they give the minimum number of comparisons needed to sort${\displaystyle n}$ items using anycomparison sort. The conjecture was disproved in 1959 byL. R. Ford Jr. andSelmer M. Johnson, who found a different sorting algorithm, the Ford–Johnsonmerge-insertion sort, using fewer comparisons.^[1]

The same sequence of sorting numbers also gives theworst-case number of comparisons used bymerge sort to sort${\displaystyle n}$ items.^[2]

The sorting numbers (shifted by one position) also give the sizes of the shortest possiblesuperpatterns for thelayered permutations.^[3]

• Integer sequences
• Comparison sorts

• Articles with short description
• Short description matches Wikidata