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 algorithms.
These numbers give the worst-case number of comparisons used by both binary insertion sort and merge sort.
th sorting number is given by the formula[1] The sequence of numbers given by this formula (starting with
th sorting number fluctuates between approximately
[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
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-insertion sort, using fewer comparisons.
[2] The sorting numbers (shifted by one position) also give the sizes of the shortest possible superpatterns for the layered permutations.