Does sorting by a non transitive comparator "work"?

Question

What will happen if I supply a non-transitive Comparator to Collections.sort? Can I run into infinite loop?

A small test I wrote produced an output, but I want to make sure this will always be the case.

The problem is that in some cases, my comparator can produce cycles, and in this case I just want to make sure it will not run into infinite loop. I don't care about the actual result.

Answer 1

The Java docs say that you must make sure that your comparator is transitive. If you supply a comparator that doesn't adhere to what was requested, all bets are off. It might work for a given implementation but might crash horribly (std::sort in C++ does) in another.

In short, you shouldn't rely on it working even if it does for some or other examples.

Answer 2

Since Java 7 Collections.sort uses TimSort. Using a non-transitive comparator for sorting in Java >= 7 will throw the following exception:

java.lang.IllegalArgumentException: Comparison method violates its general contract!

Answer 3

The Collections.sort() is based on a mergesort.

a mergesort has a O(logn) iterations overall, because the array size is ALWAYS divided, so the sort() should end, regardless the Comparator is not not transitive, so infinite loop won't occur.

Though, there are no guarantees on the resulted List's order.

Answer 4

The behaviour of Collections.sort in this case is implementation dependant. The Java 6 SE implementation uses a combination of Mergesort and Insertionsort which are both deterministic with non-transitive comparators but in Java 7 the Timsort algorithm gets used and other implementations might use Quicksort or something else, so you can't be sure that it will work with all implementations.