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" 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:

1. if a ≤ b and b ≤ a then a = b (antisymmetry)
2. if a ≤ b and b ≤ c then a ≤ c (transitivity)
3. a ≤ b or b ≤ a (totalness or trichotomy)

Examples

Some of the most well-known comparison sorts include:

• Quicksort
• Heapsort
• Merge sort
• Introsort
• Insertion sort
• Selection sort
• Bubble sort

Some examples of sorts which are not comparison sorts include:

• Radix sort (examines individual bits of keys)
• Counting sort (indexes using key values)
• Bucket sort (examines bits of keys)

Performance limits

There are fundamental limits on the performance of comparison sorts. A comparison sort must have an upper bound of at least Ω(n log n) comparison operations in the worst case. This is a consequence of the limited information available through comparisons alone. 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).

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: function compare((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.

Proof sketch of lower bound

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. Therefore, if we don't perform enough comparisons to distinguish n! different lists, we can't have a correct sort.

But how many comparisons is this? We can think of the control flow of a comparison sort algorithm as following a very large conceptual binary tree, where each node represents a comparison between two list elements. There are n! leaves in this tree corresponding to the n! permutations; when we reach a leaf, we have derived enough information to successfully sort the list. The worst-case time of the algorithm is the maximum distance of any leaf from the root, called the height of the tree. Although the specific tree depends on the sorting algorithm, any tree with n! leaves has height at least as large as the complete binary tree with n! leaves. This tree has Ω(log(n!)) height. But Stirling's approximation tells us that log(n!) is Ω(n log n).

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 0262032937. Section 8.1: Lower bounds for sorting, pp.165–168.

Sort algorithms