Sorting number

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.

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

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

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

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

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

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

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 ${\displaystyle n}${\displaystyle n} 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.^[1]

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

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

• Integer sequences
• Comparison sorts

• Articles with short description
• Short description matches Wikidata