10

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.

Joachim Sauer
  • 302,674
  • 57
  • 556
  • 614
duduamar
  • 3,816
  • 7
  • 35
  • 54
  • 2
    Maybe post some relevant code? – pap Oct 31 '11 at 08:19
  • 2
    This is a general question, not relevant to a specific code - the question is what is the behavior if I provide a comparator that is not transitive to Collections.sort – duduamar Oct 31 '11 at 08:21
  • 2
    The behaviour of using a non-transitive `Comparator` is not defined, as a non-transitive `Comparator` is **not properly implemented**. In practice, I'm *pretty* sure that `Collections.sort()` will *not* run in an infinite loop, even if the `Comparator` is broken. But nothing in the specifications *requires* this behaviour. – Joachim Sauer Oct 31 '11 at 08:25

5 Answers5

7

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.

Pablo
  • 8,644
  • 2
  • 39
  • 29
  • Hi Pablo. I'm sorry to hijack a comment, but I've asked a question here: https://stackoverflow.com/questions/45599509/why-does-stdsort-segfault-with-non-transitive-comparators You have apparently faced the issue I'm facing today, where C++ std::sort crashes with a non-transitive comparator. I was wondering if you knew why? Again, sorry to hijack a 6-year-old-comment, but very little data exists on this subject. – Mike B Aug 09 '17 at 22:48
4

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!
Martin
  • 111
  • 1
  • 3
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.

amit
  • 175,853
  • 27
  • 231
  • 333
2

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.

x4u
  • 13,877
  • 6
  • 48
  • 58
0

First of all, I suggest you to think about comparision - is the compassion operation really equivalence relation. If you accept that it is not and it must be - track compared objects in some local variable. This local variable may be compared objects or Thread Local variable. This Variable may be the set of objects pair compared. Inside compare method invocation check if this pair was visited - if true, decide what to do. But take car about Set of objects visited - it should really contain something like hash or object id, because you can go to infinity in other way. And also take into consideration that storing compared pair in local variable is memory consuming.

Max
  • 842
  • 5
  • 16