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) [Transitive relation]
- for all a and b, a ≤ b or b ≤ a (connexity) [Connected relationship].
It is possible that both a ≤ b and b ≤ a; in this case either may come first in the sorted list. In a Stable sorting algorithm, the input order determines the sorted order in this case.