Comparison sort

Quicksort in action on a list of numbers. The horizontal lines are pivot values.

Some of the most well-known comparison sorts include:

• Quicksort
• Heapsort
• Shellsort
• Merge sort
• Introsort
• Insertion sort
• Selection sort
• Bubble sort
• Odd–even sort
• Cocktail shaker sort
• Cycle sort
• Merge-insertion sort
• Smoothsort
• Timsort
• Block sort

There are fundamental limits on the performance of comparison sorts. A comparison sort must have an average-case lower bound of Ω(n log n) comparison operations,[1] which is known as linearithmic time. This is a consequence of the limited information available through comparisons alone — or, to put it differently, of the vague algebraic structure of totally ordered sets. In this sense, mergesort, heapsort, and introsort are asymptotically optimal in terms of the number of comparisons they must perform, although this metric neglects other operations. Non-comparison sorts (such as the examples discussed below) can achieve O(n) performance by using operations other than comparisons, allowing them to sidestep this lower bound (assuming elements are constant-sized).

Comparison sorts may run faster on some lists; many adaptive sorts such as insertion sort run in O(n) time on an already-sorted or nearly-sorted list. The Ω(n log n) lower bound applies only to the case in which the input list can be in any possible order.

Real-world measures of sorting speed may need to take into account the ability of some algorithms to optimally use relatively fast cached computer memory, or the application may benefit from sorting methods where sorted data begins to appear to the user quickly (and then user's speed of reading will be the limiting factor) as opposed to sorting methods where no output is available until the whole list is sorted.

Despite these limitations, comparison sorts offer the notable practical advantage that control over the comparison function allows sorting of many different datatypes and fine control over how the list is sorted. For example, reversing the result of the comparison function allows the list to be sorted in reverse; and one can sort a list of tuples in lexicographic order by just creating a comparison function that compares each part in sequence:

function tupleCompare((lefta, leftb, leftc), (righta, rightb, rightc))
    if lefta ≠ righta
        return compare(lefta, righta)
    else if leftb ≠ rightb
        return compare(leftb, rightb)
    else
        return compare(leftc, rightc)

Comparison sorts generally adapt more easily to complex orders such as the order of floating-point numbers. Additionally, once a comparison function is written, any comparison sort can be used without modification; non-comparison sorts typically require specialized versions for each datatype.

This flexibility, together with the efficiency of the above comparison sorting algorithms on modern computers, has led to widespread preference for comparison sorts in most practical work.

Some sorting problems admit a strictly faster solution than the Ω(n log n) bound for comparison sorting by using non-comparison sorts; an example is integer sorting, where all keys are integers. When the keys form a small (compared to n) range, counting sort is an example algorithm that runs in linear time. Other integer sorting algorithms, such as radix sort, are not asymptotically faster than comparison sorting, but can be faster in practice.

The problem of sorting pairs of numbers by their sum is not subject to the Ω(n² log n) bound either (the square resulting from the pairing up); the best known algorithm still takes O(n² log n) time, but only O(n²) comparisons.

n	${\displaystyle \left\lceil \log _{2}(n!)\right\rceil }$	Minimum
1	0	0
2	1	1
3	3	3
4	5	5
5	7	7
6	10	10
7	13	13
8	16	16
9	19	19
10	22	22
11	26	26
12	29	30[2][3]
13	33	34[4][5][6]
14	37	38[6]
15	41	42[7][8][9]
16	45	46[10]
17	49	50[10]
18	53	54[10]
19	57	58[9]
20	62	62
21	66	66
22	70	71[6]
n	${\displaystyle \left\lceil \log _{2}(n!)\right\rceil }$	${\displaystyle n\log _{2}n-{\frac {n}{\ln 2}}}$
10	22	19
100	525	521
1 000	8 530	8 524
10 000	118 459	118 451
100 000	1 516 705	1 516 695
1 000 000	18 488 885	18 488 874

Above: A comparison of the lower bound ${\displaystyle \left\lceil \log _{2}(n!)\right\rceil }$ to the actual minimum number of comparisons (from OEIS: A036604) required to sort a list of n items (for the worst case). Below: Using Stirling's approximation, this lower bound is well-approximated by ${\displaystyle n\log _{2}n-{\frac {n}{\ln 2}}}$.

The number of comparisons that a comparison sort algorithm requires increases in proportion to ${\displaystyle n\log(n)}$, where ${\displaystyle n}$ is the number of elements to sort. This bound is asymptotically tight.

Given a list of distinct numbers (we can assume this because this is a worst-case analysis), there are ${\displaystyle n}$ factorial permutations exactly one of which is the list in sorted order. The sort algorithm must gain enough information from the comparisons to identify the correct permutation. If the algorithm always completes after at most ${\displaystyle f(n)}$ steps, it cannot distinguish more than ${\displaystyle 2^{f(n)}}$ cases because the keys are distinct and each comparison has only two possible outcomes. Therefore,

${\displaystyle 2^{f(n)}\geq n!}$, or equivalently ${\displaystyle f(n)\geq \log _{2}(n!).}$

By looking at the first ${\displaystyle n/2}$ factors of ${\displaystyle n!=n(n-1)\cdots 1}$, we obtain

${\displaystyle \log _{2}(n!)\geq \log _{2}\left(\left({\frac {n}{2}}\right)^{\frac {n}{2}}\right)={\frac {n}{2}}{\frac {\log n}{\log 2}}-{\frac {n}{2}}=\Theta (n\log n).}$

${\displaystyle \log _{2}(n!)=\Omega (n\log n).}$

This provides the lower-bound part of the claim. A more precise bound can be given via Stirling's approximation. An upper bound of the same form, with the same leading term as the bound obtained from Stirling's approximation, follows from the existence of the algorithms that attain this bound in the worst case, like merge sort.

The above argument provides an absolute, rather than only asymptotic lower bound on the number of comparisons, namely ${\displaystyle \left\lceil \log _{2}(n!)\right\rceil }$ comparisons. This lower bound is fairly good (it can be approached within a linear tolerance by a simple merge sort), but it is known to be inexact. For example, ${\displaystyle \left\lceil \log _{2}(13!)\right\rceil =33}$, but the minimal number of comparisons to sort 13 elements has been proved to be 34.

Determining the exact number of comparisons needed to sort a given number of entries is a computationally hard problem even for small n, and no simple formula for the solution is known. For some of the few concrete values that have been computed, see OEIS: A036604.

(1) = = = = = = = =

(2) =   =   =   =     // max 1 compares (size1+size2-1), 4x repeats to concat 8 arrays with size 1 and 1
   === === === ===

(3)   =       =       // max 7 compares, 2x repeats to concat 4 arrays with size 2 and 2
     ===     ===  
    =====   ===== 
   ======= =======

(4)                   // max 15 compares, 1x repeats to concat 2 arrays with size 4 and 4

Formula extraction:
n = 256 = 2^8 (array size in format 2^k, for simplify)
On = (n-1) + 2(n/2-1) + 4(n/4-1) + 8(n/8-1) + 16(n/16-1) + 32(n/32-1) + 64(n/64-1) + 128(n/128-1)
On = (n-1) + (n-2) + (n-4) + (n-8) + (n-16) + (n-32) + (n-64) + (n-128)
On = n+n+n+n+n+n+n+n - (1+2+4+8+16+32+64+128)   | 1+2+4... = formula for geometric sequence Sn = a1 * (q^i - 1) / (n - 1), n is number of items, a1 is first item
On = 8*n - 1 * (2^8 - 1) / (2 - 1)
On = 8*n - (2^8 - 1)   | 2^8 = n
On = 8*n - (n - 1)
On = (8-1)*n + 1   | 8 = ln(n)/ln(2) = ln(256)/ln(2)
On = (ln(n)/ln(2) - 1) * n + 1

Example:
n = 2^4 = 16, On ~= 3*n
n = 2^8 = 256, On ~= 7*n
n = 2^10 = 1.024, On ~= 9*n
n = 2^20 = 1.048.576, On ~= 19*n

• Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 5.3.1: Minimum-Comparison Sorting, pp. 180–197.