mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

and

computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...

, the sorting numbers are a sequence of numbers introduced in 1950 by

Hugo Steinhaus Hugo Dyonizy Steinhaus ( , ; 14 January 1887 – 25 February 1972) was a Polish mathematician and educator. Steinhaus obtained his PhD under David Hilbert at Göttingen University in 1911 and later became a professor at the Jan Kazimierz Univers ...

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 In computer science, best, worst, and average cases of a given algorithm express what the resource usage is ''at least'', ''at most'' and ''on average'', respectively. Usually the resource being considered is running time, i.e. time complexity, b ...

number of comparisons used by both binary insertion sort and

merge sort In computer science, merge sort (also commonly spelled as mergesort and as ) is an efficient, general-purpose, and comparison sort, comparison-based sorting algorithm. Most implementations of merge sort are Sorting algorithm#Stability, stable, wh ...

. However, there are other

algorithms In mathematics and computer science, an algorithm () is a finite sequence of mathematically rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for per ...

that use fewer comparisons.

Formula and examples

The

n

th sorting number is given by the formula The sequence of numbers given by this formula (starting with

n = 1

) is 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 parameter ...

, :

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 In analytic geometry, an asymptote () of a curve is a line such that the distance between the curve and the line approaches zero as one or both of the ''x'' or ''y'' coordinates tends to infinity. In projective geometry and related contexts, ...

, 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 2, two as the Base (exponentiation), base and integer as the exponent. In the fast-growing hierarchy, is exactly equal to f_1^ ...

Application to sorting

In 1950,

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

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-insertion sort, using fewer comparisons. The same sequence of sorting numbers also gives the

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