Why is my comparison method violating its general contract?

Question

Exception in thread "main" java.lang.IllegalArgumentException: 
Comparison method violates its general contract!
    at java.util.ComparableTimSort.mergeLo(ComparableTimSort.java:744)
    at java.util.ComparableTimSort.mergeAt(ComparableTimSort.java:481)
    at java.util.ComparableTimSort.mergeCollapse(ComparableTimSort.java:406)
    at java.util.ComparableTimSort.sort(ComparableTimSort.java:213)
    at java.util.Arrays.sort(Arrays.java:1246)
    at Solution.main(Solution.java:16)

This is the exception I get when running my program. Error occurs when I am using Arrays.sort function on an array of objects of class Element described as

static class Element implements Comparable<Element> {
    int pos,val;
    Element(int pos,int val){
        this.pos=pos;
        this.val=val;
    }
    public int compareTo(Element a){
        if(val!=a.val)
            return val-a.val;
        return pos-a.pos;
    }
}

It runs perfectly fine in some cases but throws the above error in other cases. What is the error in my program? Why is my comparison method violating its general contract?

Eran · Accepted Answer · 2017-12-24T08:31:02.350

The subtractions in your compareTo method may cause numerical overflow for some inputs, which can break the general contract.

Change it to:

public int compareTo(Element a){
    if(val != a.val)
        return Integer.compare(val,a.val);
    return Integer.compare(pos,a.pos);
}

Comparable<T> requires that the relation defined by compareTo be transitive:

The implementor must also ensure that the relation is transitive: (x.compareTo(y)>0 && y.compareTo(z)>0) implies x.compareTo(z)>0.

Now consider three instances of Element having the following values of val:

Element    val
-------    --------------------
x          11
y          Integer.MIN_VALUE+20
z          Integer.MIN_VALUE+10

Now, let's compute what your method would return:

x.compareTo(y) returns 2147483639 > 0
y.compareTo(z) returns 10 > 0

but

x.compareTo(z) returns -2147483647 (overflow) < 0

Hence your method does not satisfy transitivity.

Why is my comparison method violating its general contract?

1 Answers1