Jump to content

Sorting number

From Wikipedia, the free encyclopedia

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 nth sorting number is given by the formula[1]

n⌈log2n⌉−2⌈log2n⌉+1.

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

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

A(n)=A(⌊n/2⌋)+A(⌈n/2⌉)+n−1.

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

Asymptotically, the value of the nth sorting number fluctuates between approximately nlog2n−n and nlog2n−0.915n, depending on the ratio between n 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 n 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.[1]

The same sequence of sorting numbers also gives the worst-case number of comparisons used by merge sort to sort n 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. 1 2 3 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. 1 2 3 Allouche, Jean-Paul; Shallit, Jeffrey (1992), "The ring of k-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