Is transitivity required for a sorting algorithm Is it possible to use a sorting algorithm with a non-transitive comparison, and if yes, why is transitivity listed as a requirement for sorting comparators?

Background:


A sorting algorithm generally sorts the elements of a
list according to a comparator function C(x,y), with

\begin{array}{ll} C(x,y) = \begin{cases}
-1  &amp; {\text{if}}\ x\prec y   \\ 0 &amp; {\text{if}}\ x\sim y \\ 
+1 &amp; {\text{if}}\ x\succ y  \\ \end{cases} \end{array}

The requirements for this comparator are, as far as I
understand them:


reflexive: $\forall x: C(x,x)=0$ 
antisymmetric: $\forall x,y: C(x,y) = - C(y,x)$ 
transitive: $\forall x,y,z, a: C(x,y)=a \land C(y,z)=a \Rightarrow C(x,z)=a$
C(x,y) is defined for all x and y, and the results depend only on x and y


(These requirements are always listed differently accross different
implementations, so I am not sure I got them all right)


Now I am wondering about a "tolerant" comparator function, that accepts numbers x,y as similar if$ |x - y| \le 1$:
\begin{array}{ll}
C(x,y) = \begin{cases}
-1  &amp; {\text{if}}\ x\lt y-1   \\
0 &amp; {\text{if}}\ |x - y| \le 1 \\ 
+1 &amp; {\text{if}}\ x\gt y+1  \\
\end{cases}
\end{array}

Examples: both [ 1, 2, 3, 4, 5] and [1, 4, 3, 2, 5] are correctly sorted  in ascending order according to the tolerant comparator ($C(x,y) \le 0$ if x comes before y in the list)
but [1, 4, 2, 3, 5] is not, since C(4,2)=1

This tolerant comparator is reflexive and antisymmetric, but not transitive.

i.e. C(1,2) = 0 , c(2,3) = 0, but C(1,3) = -1, violating transitivity

Yet I cannot think of any sorting algorithm that would fail to produce a "correctly sorted" output when given this comparator and a random list.

Is transitivity therefore not required in this case? And is there a less strict version of transitivity that is required for the sorting to work?

Related questions:


Why is antisymmetry necessary for comparison sort? (about antisymmetry)
Sorting algorithms which accept a random comparator (about a random C(x,y))
OrderBy with a non-transitive IComparer (about the c# sort algorithm, by me)
You asked: Can we run a sorting algorithm, feeding it a non-transitive comparator?

The answer: Of course.  You can run any algorithm with any input.

However, you know the rule: Garbage In, Garbage Out.  If you run a sorting algorithm with a non-transitive comparator, you might get nonsense output.  In particular, there is no guarantee that the output will be "sorted" according to your comparator.  So, running a sorting algorithm with a non-transitive comparator is not likely to be useful in the way you were probably hoping for.

As a counterexample, running insertion sort on the input list $[3, 2, 1]$ using your comparator would leave the list unchanged -- yet the resulting output list is not in sorted order (according to your comparator).