Sorting number

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 the recurrence relation^[2],

${\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}$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]