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 obey two of the properties of a
total order:
- if a = b and b = c then a = c (transitivity)
- for all a and b, either a = b or b = a (totalness or trichotomy).