A **comparison sort** is a particular type of sorting algorithm; a number of well-known algorithms are comparison sorts. It is defined as a sorting algorithm which can only read the list elements through a single abstract comparison operation (often a "less than or equal to" operator) that determines which of two elements should occur first in the final sorted list. The only requirement is that the operator obey the three defining properties of a total order: In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ...
In mathematics, a total order, linear order or simple order on a set X is any binary relation on X that is antisymmetric, transitive, and total. ...
- if
*a* ≤ *b* and *b* ≤ *a* then *a* = *b* (antisymmetry) - if
*a* ≤ *b* and *b* ≤ *c* then *a* ≤ *c* (transitivity) *a* ≤ *b* or *b* ≤ *a* (totalness or trichotomy) A trichotomy is a splitting into three parts, and, apart from its normal literal meaning, can refer to: trichotomy (mathematics), in the mathematical field of order theory trichotomy (philosophy), for the idea that man has a threefold nature In taxonomy, a trichotomy is speciation of three groups from a common...
## Examples
Some of the most well-known comparison sorts include: Some examples of sorts which are not comparison sorts include: Quicksort in action on a list of random numbers. ...
A run of the heapsort algorithm sorting an array of randomly permutated values. ...
A merge sort algorithm used to sort an array of 7 integer values. ...
Introsort or introspective sort is a sorting algorithm designed by David Musser in 1997. ...
Insertion sort is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time. ...
Selection sort is a sorting algorithm, specifically an in-place comparison sort. ...
Bubble sort, sometimes shortened to bubblesort, also known as exchange sort, is a simple sorting algorithm. ...
==Performance limits a To meet Wikipedias quality standards, this article may require cleanup. ...
Counting sort is a sorting algorithm which (like bucket sort) takes advantage of knowing the range of the numbers in the array to be sorted (array A). ...
Bucket sort is a sort algorithm that works by partitioning an array into a finite number of buckets and then sorting each bucket. ...
There are fundamental limits on the performance of comparison sorts. A comparison sort must have a lower bound of Ω(*n* log *n*) comparison operations in the worst case. 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. The three non-comparison sorts above achieve O(*n*) performance by using operations other than comparisons, allowing them to sidestep this lower bound (assuming elements are constant-sized). The Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. ...
In computer science, an algorithm is said to be asymptotically optimal if, roughly speaking, for large inputs it performs at worst a constant factor worse than the best possible algorithm. ...
The Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. ...
Nevertheless, comparison sorts offer the notable 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 it's simple to sort a list of tuples in lexicographic order by just creating a comparison function that compares by each part in sequence: In mathematics, a tuple is a finite sequence (also known as an ordered list) of objects, each of a specified type. ...
In mathematics, the lexicographical order, or dictionary order, is a natural order structure of the cartesian product of two ordered sets. ...
**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) Balanced ternary notation allows comparisons to be made in one step, whose result will be one of "less than", "greater than" or "equal to". Balanced ternary is a non-standard positional numeral system, useful for comparison logic. ...
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.
## How many comparisons are needed to sort a list? The number of comparisons an optimal comparison sort algorithm needs to do increases in proportion to *n*log(*n*), where *n* is the number of elements to sort. It is easy to prove that this bound is asymptotically tight, as follows: Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ...
Imagine we're sorting a list of numbers, all distinct (we can assume this because this is a worst-case analysis). There are *n* factorial (*n*!) possible ways to rearrange this list, and each one must be rearranged differently to come up with a sorted list. Thus in order to sort correctly, the sort algorithm must gain enough information from the comparisons to distinguish between the *n*! different possibilities. As we assume distinct keys, each comparison has only two different possible outcomes, so if the algorithm always completes after at most *f*(*n*) steps, it cannot distinguish more than 2^{f(n)} cases. Therefore, for a correct comparison sort it must hold that , or equivalently . The beginning of the sequence of factorials (sequence A000142 in OEIS) In mathematics, the factorial of a number n is the product of all positive integers less than or equal to n. ...
From Stirling's approximation we know that log_{2}(*n*!) is asymptotically equal to (modulo some terms at most linear in *n*). This provides the lower-bound part of the claim. An identical upper bound follows from the well-known fact that several of the algorithms mentioned above do perform comparisons in the worst case. The relative difference between (ln x!) and (x ln x - x) approaches zero as x increases. ...
The above argument also provides an *absolute*, rather than asymptotic, lower bound on the number of comparisons, namely comparisons. This lower bound is fairly good (it can be approached within a linear tolerance by a simple merge sort), but it is known not to be exact. For example, , but the minimal number of comparisons to sort 13 elements has been proved to be 34 (Peczarski 2004). Determining the *exact* minimal number of comparisons needed to sort a given number of entries is a computationally hard problem even for relatively small *n*, and no simple formula for the solution is known. For some of the few concrete values that have been computed, see A036604.
## 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.180–197. - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
*Introduction to Algorithms*, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 8.1: Lower bounds for sorting, pp.165–168. |