Sorting number

Summary

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. However, there are other algorithms that use fewer comparisons.

Formula and examples edit

The  th sorting number is given by the formula[1]

 

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, ... (sequence A001855 in the OEIS).

The same sequence of numbers can also be obtained from the recurrence relation[2],

 

or closed form

 

It is an example of a 2-regular sequence.[2]

Asymptotically, the value of the  th sorting number fluctuates between approximately   and   depending on the ratio between   and the nearest power of two.[1]

Application to sorting edit

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-insert sort, using fewer comparisons.[1]

The same sequence of sorting numbers also gives the worst-case number of comparisons used by merge sort to sort   items.[2]

Other applications edit

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

References edit

  1. ^ a b c Ford, Lester R. Jr.; Johnson, Selmer M. (1959), "A tournament problem", American Mathematical Monthly, 66 (5): 387–389, doi:10.2307/2308750, JSTOR 2308750, MR 0103159
  2. ^ a b c Allouche, Jean-Paul; Shallit, Jeffrey (1992), "The ring of  -regular sequences", Theoretical Computer Science, 98 (2): 163–197, doi:10.1016/0304-3975(92)90001-V, MR 1166363. See Example 28, p. 192.
  3. ^ Albert, Michael; Engen, Michael; Pantone, Jay; Vatter, Vincent (2018), "Universal layered permutations", Electronic Journal of Combinatorics, 25 (3): P23:1–P23:5, arXiv:1710.04240, doi:10.37236/7386, S2CID 52100342