In mathematics and computer science, the sorting numbers are a sequence of numbers introduced in 1950 by
Hugo Steinhaus
Hugo Dyonizy Steinhaus ( ; ; January 14, 1887 – February 25, 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 Un ...
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
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
th sorting number is given by the formula
:
where
:
The sequence of numbers given by this formula (starting with
) 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 parameter ...
:
It is an example of a
2-regular sequence.
Asymptotically, the value of the
th sorting number fluctuates between approximately
and
depending on the ratio between
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-negativ ...
.
Application to sorting
In 1950,
Hugo Steinhaus
Hugo Dyonizy Steinhaus ( ; ; January 14, 1887 – February 25, 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 Un ...
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
items using any
comparison sort. The conjecture was disproved in 1959 by
L. R. Ford Jr.
Lester Randolph Ford Jr. (September 23, 1927 – February 26, 2017) was an American mathematician specializing in network flow problems. He was the son of mathematician Lester R. Ford Sr.
Ford's paper with D. R. Fulkerson on the maximum flow p ...
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
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
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 ...
to sort
items.
Other applications
The sorting numbers (shifted by one position) also give the sizes of the shortest possible
superpattern In the mathematical study of permutations and permutation patterns, a superpattern or universal permutation is a permutation that contains all of the patterns of a given length. More specifically, a ''k''-superpattern contains all possible patterns ...
s for the
layered permutations.
References
{{Classes of natural numbers
Integer sequences
Comparison sorts