Sorting number

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

${\displaystyle n\,S(n)-2^{S(n)}+1,}$

where

${\displaystyle S(n)=\lfloor 1+\log _{2}n\rfloor .}$

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

0, 1, 3, 5, 8, 11, 14, 17, 21, 25, 29, 33, 37, 41, ... (sequence A001855 in the OEIS).

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}$

or closed form

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

It is an example of a 2-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 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}$ 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-insert 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}$ items.[2]

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