View source for Comparison sort

{{Short description|Type of sorting algorithm that works by comparing pairs of elements}}
[[Image:Balance à tabac 1850.JPG|thumb|right|upright=1.1|Sorting a set of unlabelled weights by weight using only a balance scale requires a comparison sort algorithm.]]
A '''comparison sort''' is a type of [[sorting algorithm]] that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator or a [[three-way comparison]]) 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'' ([[connex relation|connexity]]).

It is possible that both ''a'' ≤ ''b'' and ''b'' ≤ ''a''; in this case either may come first in the sorted list. In a [[sorting algorithm#Stability|stable sort]], the input order determines the sorted order in this case.

Comparison sorts studied in the literature are "comparison-based".<ref name=":0">{{Cite journal |last=Wilkes |first=M. V. |date=1974-11-01 |title=The Art of Computer Programming, Volume 3, Sorting and Searching |url=http://dx.doi.org/10.1093/comjnl/17.4.324 |journal=The Computer Journal |volume=17 |issue=4 |pages=324–324 |doi=10.1093/comjnl/17.4.324 |issn=0010-4620}}</ref> Elements ''a'' and ''b'' can be swapped or otherwise re-arranged by the algorithm only when the order between these elements has been established based on the outcomes of prior comparisons. This is the case when the order between ''a'' and ''b'' can be derived via the [[transitive closure]] of these prior comparison outcomes. 

For comparison-based sorts the decision to execute basic operations other than comparisons is based on the outcome of comparisons. Hence in a time analysis the number of executed comparisons is used to determine upper bound estimates for the number of executed basic operations such as swaps or assignments.<ref name=":0" />    

A metaphor for thinking about comparison sorts is that someone has a set of unlabelled weights and a [[balance scale]]. Their goal is to line up the weights in order by their weight without any information except that obtained by placing two weights on the scale and seeing which one is heavier (or if they weigh the same).

==Examples==
[[File:Sorting quicksort anim.gif|thumb|[[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]]

==Performance limits and advantages of different sorting techniques==

There are fundamental limits on the performance of comparison sorts. A comparison sort must have an average-case lower bound of [[big-O notation|Ω]](''n'' log ''n'') comparison operations,<ref>{{Introduction to Algorithms|3|pages=191–193}}</ref> 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 [[big-O notation|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 sort]]s such as [[insertion sort]] run in O(''n'') time on an already-sorted or nearly-sorted list. The [[big-O notation|Ω]](''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 [[Random Access Memory|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 [[tuple]]s 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 number]]s. 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.

==Alternatives==
Some sorting problems admit a strictly faster solution than the {{math|Ω(''n'' log ''n'')}} bound for comparison sorting by using [[Sorting algorithm#Non-comparison sorts|non-comparison sorts]]; an example is [[integer sorting]], where all keys are integers. When the keys form a small (compared to {{mvar|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 [[X + Y sorting|sorting pairs of numbers by their sum]] is not subject to the {{math|Ω(''n''² log ''n'')}} bound either (the square resulting from the pairing up); the best known algorithm still takes {{math|O(''n''² log ''n'')}} time, but only {{math|O(''n''²)}} comparisons.

==Number of comparisons required to sort a list==
<div class="thumb tright">
<div class="thumbinner" style="width:360px;">
{| class="wikitable" style="margin-left:auto; margin-right:auto;"
! ''n'' !! <math>\left\lceil\log_2(n!)\right\rceil</math> !! Minimum
|-
|style="text-align:right;"| 1
|style="text-align:right;"| 0
|style="text-align:center;"| 0
|-
|style="text-align:right;"| 2
|style="text-align:right;"| 1
|style="text-align:center;"| 1
|-
|style="text-align:right;"| 3
|style="text-align:right;"| 3
|style="text-align:center;"| 3
|-
|style="text-align:right;"| 4
|style="text-align:right;"| 5
|style="text-align:center;"| 5
|-
|style="text-align:right;"| 5
|style="text-align:right;"| 7
|style="text-align:center;"| 7
|-
|style="text-align:right;"| 6
|style="text-align:right;"| 10
|style="text-align:center;"| 10
|-
|style="text-align:right;"| 7
|style="text-align:right;"| 13
|style="text-align:center;"| 13
|-
|style="text-align:right;"| 8
|style="text-align:right;"| 16
|style="text-align:center;"| 16
|-
|style="text-align:right;"| 9
|style="text-align:right;"| 19
|style="text-align:center;"| 19
|-
|style="text-align:right;"| 10
|style="text-align:right;"| 22
|style="text-align:center;"| 22
|-
|style="text-align:right;"| 11
|style="text-align:right;"| 26
|style="text-align:center;"| 26
|-
|style="text-align:right;"| 12
|style="text-align:right;"| 29
|style="text-align:center;"| 30<ref name="Wells1965">Mark Wells, Applications of a language for computing in combinatorics, Information Processing 65 (Proceedings of the 1965 IFIP Congress), 497–498, 1966.</ref><ref name="Wells1971">Mark Wells, Elements of Combinatorial Computing, Pergamon Press, Oxford, 1971.</ref>
|-
|style="text-align:right;"| 13
|style="text-align:right;"| 33
|style="text-align:center;"| 34<ref name="KasaiSawatoIwata1994">Takumi Kasai, Shusaku Sawato, Shigeki Iwata, Thirty four comparisons are required to sort 13 items, LNCS 792, 260-269, 1994.</ref><ref name="Peczarski2002">Marcin Peczarski, Sorting 13 elements requires 34 comparisons, LNCS 2461, 785–794, 2002.</ref><ref name="Peczarski2004">Marcin Peczarski, New results in minimum-comparison sorting, Algorithmica 40 (2), 133–145, 2004.</ref>
|-
|style="text-align:right;"| 14
|style="text-align:right;"| 37
|style="text-align:center;"| 38<ref name="Peczarski2004" />
|-
|style="text-align:right;"| 15
|style="text-align:right;"| 41
|style="text-align:center;"| 42<ref name="Peczarski2006">Marcin Peczarski, Computer assisted research of posets, PhD thesis, University of Warsaw, 2006.</ref><ref name="Peczarski2007">{{cite journal | last1 = Peczarski | first1 = Marcin | year = 2007 | title = The Ford-Johnson algorithm is still unbeaten for less than 47 elements | journal = Inf. Process. Lett. | volume = 101 | issue = 3| pages = 126–128 | doi = 10.1016/j.ipl.2006.09.001 }}</ref><ref name="ChengLiuWang2007">{{cite journal | first1 = Weiyi | last1 = Cheng | first2 = Xiaoguang | last2 = Liu | first3 = Gang | last3 = Wang | first4 = Jing | last4 = Liu | date = October 2007 | title = 最少比较排序问题中S（15）和S（19）的解决 |language=zh |trans-title=The results of S(15) and S(19) to minimum-comparison sorting problem | url = http://fcst.ceaj.org/EN/abstract/abstract47.shtml | journal = Journal of Frontiers of Computer Science and Technology | volume = 1 | issue = 3| pages = 305–313 }}<!--The PDF download works, although the web server misclassifies it as a RAR file.--></ref>
|-
|style="text-align:right;"| 16
|style="text-align:right;"| 45
|style="text-align:center;"| 46<ref name="Stober2023">Stober, F., & Weiß, A. (2023). Lower Bounds for Sorting 16, 17, and 18 Elements. In 2023 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX) (pp. 201-213). Society for Industrial and Applied Mathematics</ref>
|-
|style="text-align:right;"| 17
|style="text-align:right;"| 49
|style="text-align:center;"| 50<ref name="Stober2023" />
|-
|style="text-align:right;"| 18
|style="text-align:right;"| 53
|style="text-align:center;"| 54<ref name="Stober2023" />
|-
|style="text-align:right;"| 19
|style="text-align:right;"| 57
|style="text-align:center;"| 58<ref name="ChengLiuWang2007" />
|-
|style="text-align:right;"| 20
|style="text-align:right;"| 62
|style="text-align:center;"| 62
|-
|style="text-align:right;"| 21
|style="text-align:right;"| 66
|style="text-align:center;"| 66
|-
|style="text-align:right;"| 22
|style="text-align:right;"| 70
|style="text-align:center;"| 71<ref name="Peczarski2004" />
|-
|style="height:5px;"| || ||
|-
! ''n'' !! <math>\left\lceil\log_2(n!)\right\rceil</math> !! <math>n \log_2 n - \frac{n}{\ln 2}</math>
|-
|style="text-align:right;"| 10
|style="text-align:right;"| 22
|style="text-align:center;"| 19
|-
|style="text-align:right;"| 100
|style="text-align:right;"| 525
|style="text-align:center;"| 521
|-
|style="text-align:right;"| 1 000
|style="text-align:right;"| 8 530
|style="text-align:center;"| 8 524
|-
|style="text-align:right;"| 10 000
|style="text-align:right;"| 118 459
|style="text-align:center;"| 118 451
|-
|style="text-align:right;"| 100 000
|style="text-align:right;"| 1 516 705
|style="text-align:center;"| 1 516 695
|-
|style="text-align:right;"| {{nobr|1 000 000}}
|style="text-align:right;"| 18 488 885
|style="text-align:center;"| 18 488 874
|}
<div class="thumbcaption">
Above: A comparison of the lower bound <math>\left\lceil\log_2(n!)\right\rceil</math> to the actual minimum number of comparisons (from {{OEIS2C|id=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 <math>n \log_2 n - \frac{n}{\ln 2}</math>.</div>
</div>
</div>

The number of comparisons that a comparison sort algorithm requires increases in proportion to <math>n\log(n)</math>, where <math>n</math> is the number of elements to sort.  This bound is [[asymptotic computational complexity|asymptotically tight]].

Given a list of distinct numbers (we can assume this because this is a worst-case analysis), there are <math>n</math> [[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 <math>f(n)</math> steps, it cannot distinguish more than <math>2^{f(n)}</math> cases because the keys are distinct and each comparison has only two possible outcomes. Therefore,
:<math>2^{f(n)}\geq n!</math>, or equivalently <math>f(n)\geq\log_2(n!).</math>

By looking at the first <math>n/2</math> factors of <math>n! = n (n-1) \cdots  1</math>, we obtain
:<math>\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).</math>
:<math>\log_2(n!) =  \Omega(n \log n).</math>

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 <math>\left\lceil\log_2(n!)\right\rceil</math> 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, <math>\left\lceil\log_2(13!)\right\rceil = 33</math>, 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 {{OEIS2C|id=A036604}}.

===Lower bound for the average number of comparisons===
A similar bound applies to the average number of comparisons. Assuming that
* all keys are distinct, i.e. every comparison will give either ''a''>''b'' or ''a''<''b'', and
* the input is a random permutation, chosen uniformly from the set of all possible permutations of ''n'' elements,
it is impossible to determine which order the input is in with fewer than {{math|log<sub>2</sub>(''n''!)}} comparisons on average.

This can be most easily seen using concepts from [[information theory]]. The [[Shannon entropy]] of such a random permutation is {{math|log<sub>2</sub>(''n''!)}} bits. Since a comparison can give only two results, the maximum amount of information it provides is 1 bit. Therefore, after ''k'' comparisons the remaining entropy of the permutation, given the results of those comparisons, is at least {{math|log<sub>2</sub>(''n''!)&nbsp;−&nbsp;''k''}} bits on average. To perform the sort, complete information is needed, so the remaining entropy must be 0. It follows that ''k'' must be at least {{math|log<sub>2</sub>(''n''!)}} on average. 

The lower bound derived via information theory is phrased as 'information-theoretic lower bound'. Information-theoretic lower bound is correct but is not necessarily the strongest lower bound. And in some cases, the information-theoretic lower bound of a problem may even be far from the true lower bound. For example, the information-theoretic lower bound of selection is <math>\left\lceil\log_2(n)\right\rceil</math> whereas <math>n-1</math> comparisons are needed by an adversarial argument. The interplay between information-theoretic lower bound and the true lower bound are much like a real-valued function lower-bounding an integer function. However, this is not exactly correct when the average case is considered.

To unearth what happens while analyzing the average case, the key is that what does 'average' refer to? Averaging over what? With some knowledge of information theory, the information-theoretic lower bound averages over the set of all permutations as a whole. But any computer algorithms (under what are believed currently) must treat each permutation as an individual instance of the problem. Hence, the average lower bound we're searching for is averaged over all individual cases.

To search for the lower bound relating to the non-achievability of computers, we adopt the [[Decision tree model]]. Let's rephrase a bit of what our objective is. In the [[Decision tree model]], the lower bound to be shown is the lower bound of the average length of root-to-leaf paths of an <math>n!</math>-leaf binary tree (in which each leaf corresponds to a permutation). The minimum average length of a binary tree with a given number of leaves is achieved by a balanced full binary tree, because any other binary tree can have its path length reduced by moving a pair of leaves to a higher position. With some careful calculations, for a balanced full binary tree with <math>n!</math> leaves, the average length of root-to-leaf paths is given by 
:<math>\frac{(2n! - 2^{\lfloor \log_2 n! \rfloor + 1}) \cdot \lceil \log_2 n! \rceil + (2^{\lfloor \log_2 n! \rfloor + 1} - n!) \cdot \lfloor \log_2 n! \rfloor}{n!} = \lceil \log_2 n! \rceil + 1 - \frac{2^{\lceil \log_2 n! \rceil}}{n!}</math>

For example, for {{math|1=''n''&nbsp;=&nbsp;3}}, the information-theoretic lower bound for the average case is approximately 2.58, while the average lower bound derived via [[Decision tree model]] is 8/3, approximately 2.67.

In the case that multiple items may have the same key, there is no obvious statistical interpretation for the term "average case", so an argument like the above cannot be applied without making specific assumptions about the distribution of keys.

===n log n maximum number of comparisons for array-size in format 2^k ===
Can easy compute for real algorithm sorted-list-merging (array are sorted n-blocks with size 1, merge to 1–1 to 2, merge 2–2 to 4...).
<pre>
(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
</pre>

===Sorting a pre-sorted list===
{{Main|Adaptive sort}}
If a list is already close to sorted, according to some measure of sortedness, the number of comparisons required to sort it can be smaller. An [[adaptive sort]] takes advantage of this "presortedness" and runs more quickly on nearly-sorted inputs, often while still maintaining an <math>O(n\log n)</math> worst case time bound. An example is [[adaptive heap sort]], a sorting algorithm based on [[Cartesian tree]]s. It takes time <math>O(n\log k)</math>, where <math>k</math> is the average, over all values <math>x</math> in the sequence, of the number of times the sequence jumps from below <math>x</math> to above <math>x</math> or vice versa.<ref>{{citation
 | last1 = Levcopoulos | first1 = Christos
 | last2 = Petersson | first2 = Ola
 | contribution = Heapsort - Adapted for Presorted Files
 | doi = 10.1007/3-540-51542-9_41
 | location = London, UK
 | pages = 499–509
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | title = WADS '89: Proceedings of the Workshop on Algorithms and Data Structures
 | volume = 382
 | year = 1989}}.</ref>

==Notes==
<ref>{{Cite book |last=Knuth |first=Donald E. |url=https://dl.acm.org/doi/10.5555/280635 |title=The art of computer programming,  volume 3: (2nd ed.) sorting and searching |date=1998 |publisher=Addison Wesley Longman Publishing Co., Inc. |isbn=978-0-201-89685-5 |location=USA}}</ref>

==Notes==
{{reflist}}

==References==
* [[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.&nbsp;180–197.

{{sorting}}

{{DEFAULTSORT:Comparison Sort}}
[[Category:Comparison_sorts| ]]