Encyclopedia

Sorting number

Worst-case number of comparisons used by sorting algorithms

Wikipedia contributorsAdapted for Fathomly · View authors

1 min read
Source updated December 17, 2025

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.

01Formula and examples

The $n$ th sorting number is given by the formula

$\displaystyle n\lceil \log _{2}n\rceil -2^{\lceil \log _{2}n\rceil }+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,

$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, 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.

02Application to sorting

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.

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

03Other applications

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

Watch videos about Sorting numberExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Sorting number”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.