Have you seen this before in person? It would make a great blog post.
I haven't personally encountered a buggy comparator without a total order.
I haven't personally encountered a buggy comparator without a total order.
I recently wrote a blog post which (while not the main focus) includes a discussion on randomized testing of sort algorithms in the face of inconsistent comparators: https://sunshowers.io/posts/monads-through-pbt/ section 2.
To give one example, a common error is to compare two int values via subtraction, which can give incorrect results due to overflow and modulo semantics, instead of using Integer::compare (or some equivalent of its implementation).
Another common source of comparator bugs is when people compare floats or doubles and they don’t account for NaN, which is unequal to everything, including itself!
In Java, the usual symptom of comparator bugs is that sort throws the infamous “Comparison method violates its general contract!” exception.