Sorting number

Last updated June 09, 2024

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

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

\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 ^[2],

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.^[2]

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.^[1]

Application 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-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 $n$ items.^[2]

Other applications

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

Related Research Articles

<span class="mw-page-title-main">Merge sort</span> Divide and conquer sorting algorithm

In computer science, merge sort is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the relative order of equal elements is the same in the input and output. Merge sort is a divide-and-conquer algorithm that was invented by John von Neumann in 1945. A detailed description and analysis of bottom-up merge sort appeared in a report by Goldstine and von Neumann as early as 1948.

<span class="mw-page-title-main">Sorting algorithm</span> Algorithm that arranges lists in order

In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. Efficient sorting is important for optimizing the efficiency of other algorithms that require input data to be in sorted lists. Sorting is also often useful for canonicalizing data and for producing human-readable output.

In mathematics, the floor function (or greatest integer function) is the function that takes as input a real number $x$ , and gives as output the greatest integer less than or equal to $x$ , denoted $⌊ x ⌋$ or $floor(x)$ . Similarly, the ceiling function maps $x$ to the smallest integer greater than or equal to $x$ , denoted $⌈ x ⌉$ or $ceil(x)$ .

<span class="mw-page-title-main">Shellsort</span> Sorting algorithm which uses multiple comparison intervals

Shellsort, also known as Shell sort or Shell's method, is an in-place comparison sort. It can be seen as either a generalization of sorting by exchange or sorting by insertion. The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. By starting with far-apart elements, it can move some out-of-place elements into the position faster than a simple nearest-neighbor exchange. Donald Shell published the first version of this sort in 1959. The running time of Shellsort is heavily dependent on the gap sequence it uses. For many practical variants, determining their time complexity remains an open problem.

In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height small in the face of arbitrary item insertions and deletions. These operations when designed for a self-balancing binary search tree, contain precautionary measures against boundlessly increasing tree height, so that these abstract data structures receive the attribute "self-balancing".

In computer science, a selection algorithm is an algorithm for finding the $th smallest value in a collection of ordered values, such as numbers. The value that it finds is called the th order statistic. Selection includes as special cases the problems of finding the minimum, median, and maximum element in the collection. Selection algorithms include quickselect, and the median of medians algorithm. When applied to a collection of values, these algorithms take linear time, as expressed using big O notation. For data that is already structured, faster algorithms may be possible; as an extreme case, selection in an already-sorted array takes time .$

Poly1305 is a universal hash family designed by Daniel J. Bernstein for use in cryptography.

The Steinhaus–Johnson–Trotter algorithm or Johnson–Trotter algorithm, also called plain changes, is an algorithm named after Hugo Steinhaus, Selmer M. Johnson and Hale F. Trotter that generates all of the permutations of $elements. Each two adjacent permutations in the resulting sequence differ by swapping two adjacent permuted elements. Equivalently, this algorithm finds a Hamiltonian cycle in the permutohedron, a polytope whose vertices represent permutations and whose edges represent swaps.$

Bitonic mergesort is a parallel algorithm for sorting. It is also used as a construction method for building a sorting network. The algorithm was devised by Ken Batcher. The resulting sorting networks consist of $comparators and have a delay of, where is the number of items to be sorted. This makes it a popular choice for sorting large numbers of elements on an architecture which itself contains a large number of parallel execution units running in lockstep, such as a typical GPU.$

A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation that determines which of two elements should occur first in the final sorted list. The only requirement is that the operator forms a total preorder over the data, with:

if a ≤ b and b ≤ c then a ≤ c (transitivity)
for all a and b, a ≤ b or b ≤ a (connexity).

In computer science and graph theory, Karger's algorithm is a randomized algorithm to compute a minimum cut of a connected graph. It was invented by David Karger and first published in 1993.

Discrepancy of hypergraphs is an area of discrepancy theory.

In computer science and discrete mathematics, an inversion in a sequence is a pair of elements that are out of their natural order.

In computational complexity the decision tree model is the model of computation in which an algorithm is considered to be basically a decision tree, i.e., a sequence of queries or tests that are done adaptively, so the outcome of previous tests can influence the tests performed next.

A Gilbreath shuffle is a way to shuffle a deck of cards, named after mathematician Norman Gilbreath. Gilbreath's principle describes the properties of a deck that are preserved by this type of shuffle, and a Gilbreath permutation is a permutation that can be formed by a Gilbreath shuffle.

In computer science, splaysort is an adaptive comparison sorting algorithm based on the splay tree data structure.

In computer science, an exponential search is an algorithm, created by Jon Bentley and Andrew Chi-Chih Yao in 1976, for searching sorted, unbounded/infinite lists. There are numerous ways to implement this, with the most common being to determine a range that the search key resides in and performing a binary search within that range. This takes O(log i) where i is the position of the search key in the list, if the search key is in the list, or the position where the search key should be, if the search key is not in the list.

In the mathematics of permutations, a layered permutation is a permutation that reverses contiguous blocks of elements. Equivalently, it is the direct sum of decreasing permutations.

In computer science, merge-insertion sort or the Ford–Johnson algorithm is a comparison sorting algorithm published in 1959 by L. R. Ford Jr. and Selmer M. Johnson. It uses fewer comparisons in the worst case than the best previously known algorithms, binary insertion sort and merge sort, and for 20 years it was the sorting algorithm with the fewest known comparisons. Although not of practical significance, it remains of theoretical interest in connection with the problem of sorting with a minimum number of comparisons. The same algorithm may have also been independently discovered by Stanisław Trybuła and Czen Ping.

In mathematics, a Stanley sequence is an integer sequence generated by a greedy algorithm that chooses the sequence members to avoid arithmetic progressions. If $is a finite set of non-negative integers on which no three elements form an arithmetic progression, then the Stanley sequence generated from starts from the elements of, in sorted order, and then repeatedly chooses each successive element of the sequence to be a number that is larger than the already-chosen numbers and does not form any three-term arithmetic progression with them. These sequences are named after Richard P. Stanley.$

References

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
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.
↑ 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

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[fj-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

[as-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.

[aepv-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

[1]

[2]

[3]