"Comparison method violates its general contract" is thrown only in certain cases

Question

First of all I know that this issue was described in many other threads. However I was not able to find and answer to the question, why this error is not always thrown?

Let me describe what I mean. I have written some sample code to illustrate this :

public class Mushroom {

    public int size;

    public Mushroom(int size) {
        this.size = size;
    }

    @Override
    public boolean equals(Object obj) {
        //this is intentionally false - read in description
        return false;
    }
}

dsa

public class MushroomComparator implements Comparator<Mushroom> {

    @Override
    public int compare(Mushroom o1, Mushroom o2) {
        // here is the code which breaks the contract
         if (o1.size < o2.size){
             return 1;
         }else if(o1.size >o2.size){
             return -1;
         }
         return 1;
    }

}

and finally test for comparison:

public class ComparisonTest {
    public static void main(String[] args) {
//      System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");
    List<Mushroom> forest = new ArrayList<>();

        for(int i =0; i<18; i++){
            Mushroom mushroom1 = new Mushroom(1);
            Mushroom mushroom2 = new Mushroom(3);
            Mushroom mushroom3 = new Mushroom(2);

            forest.add(mushroom1);
            forest.add(mushroom2);
            forest.add(mushroom3);

        }
        Collections.sort(forest, new MushroomComparator());
    }
}

During runtime we will receive this described issue

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

According to documentation of Collections.sort method :

(optional) if the implementation detects that the natural ordering of the list elements is found to violate the Comparable contract

So let's answer the question what is this contract in documentation of Comparable (in my example I use Comparator, but from the documentation it should fulfill the same requirements)

The implementor must ensure sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) for all x and y

This rule I intentionally break to get error about which I'm writing about. This is one of the rule which implementation of compareTo method should follow. The rest of them are described in documentation, but generally speaking as I understand well documentation equivalence relation should be fulfilled

It follows immediately from the contract for compareTo that the quotient is an equivalence relation on C, and that the natural ordering is a total order on C

What is now what really bothers me is a result of change to iterations number in my test method. If you change number from 18 to 22 then ... exception will not be thrown. This exception is described as Optional so it does mean that sometimes this exception will be thrown, and sometimes no. I was not diving deeply into new implementation of sorting algorithm (TimSort) (change of sort agorithm since Java 7). I understand that it could be mabye some CPU consuming to check every set of data for breaking comparator contract, but what is an intetion to sometimes shows that and sometimes no. It could be really missleading.

Morover I can change the implementation of compare method to simply .. return 1. According to the documentation it should break the contract. But it isn't. In documentation stays also something about the contract with equals method but it not really needed

It is strongly recommended, but not strictly required that (x.compareTo(y)==0) == (x.equals(y))

And to check it in my example I've implemented equals method to return always false. With this I was sure that equals method doesn't impose on breaking comparator contract.

Now my question is : What is really contract of comparator (in context of breaking it) ? Why for some set of data this exception is thrown and for other not ? Maybe I'm missing something ? And last but not least - which rules exatcly need to be broken to throw this exception ?

Just to note, solution for this, could be turning off this new implementation of sort algorithm what is described here and commented in my sample code.

Answer 1

why this error is not always thrown

Because it's not the job of Collections.sort to validate your comparison method. Its job is simply to implement the sort. But the logic of doing so can reveal an invalid comparison method as a by-product of its logic in certain conditional branches. And in that case it makes sense to throw rather than attempting to continue to sort with an invalid comparison method.

What is really contract of comparator (in context of breaking it) ?

That if you break the contract, sort may not function correctly, or at all. (Not that it will validate your comparison method.)

Why for some set of data this exception is thrown and for other not ?

If the sort doesn't happen to follow a path that leads to a logical flaw that the sorting code can detect, it won't know to throw. But the TimSort being used does happen to go down a logical branch which reveals the invalid comparison method, so it does throw.