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 & {\text{if}}\ x\prec y \\ 0 & {\text{if}}\ x\sim y \\
+1 & {\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 & {\text{if}}\ x\lt y-1 \\
0 & {\text{if}}\ |x - y| \le 1 \\
+1 & {\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

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).

StackExchange Computer Science Q#19013, answer score: 13