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 A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator or a three-way comparison) that determines which of two elements should oc ...

algorithms. These numbers give the worst-case number of comparisons used by both

binary insertion sort Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time by comparisons. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. Howev ...

and

merge sort In computer science, merge sort (also commonly spelled as mergesort) is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same ...

. However there are other algorithms that use fewer comparisons.

Formula and examples

The

n

th sorting number is given by the formula :

n\,S(n)-2^+1

where :

S(n)=\lfloor 1 + \log_2 n \rfloor.

The sequence of numbers given by this formula (starting with

n=1

) is :0, 1, 3, 5, 8, 11, 14, 17, 21, 25, 29, 33, 37, 41, ... . The same sequence of numbers can also be obtained from the

recurrence relation In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a paramete ...

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. Asymptotically, the value of the

n

th sorting number fluctuates between approximately

n\log_2 n-n

and

n\log_2 n-0.915n

depending on the ratio between

n

and the nearest

power of two A power of two is a number of the form where is an integer, that is, the result of exponentiation with number two as the base and integer as the exponent. In a context where only integers are considered, is restricted to non-negati ...

Application to sorting

In 1950, Hugo Steinhaus observed that these numbers count the number of comparisons used by

, and conjectured (incorrectly) that they give the minimum number of comparisons needed to sort

n

items using any

. 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. The same sequence of sorting numbers also gives the worst-case number of comparisons used by

to sort

n

items.

Other applications

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

References

{{Classes of natural numbers Integer sequences Comparison sorts