Collections.sort() throws Comparison method violates its general contract! exception

Question

I'm trying to sort a List<> object and I get this exception thrown (for large lists only though)

sorting code:

List<FinalSentence> sentenceList = finalRepresentation.getSentences();
Collections.sort(sentenceList); // <=== EXCEPTION THROWN HERE!!!

FinalSentence class header:

public class FinalSentence implements Comparable<FinalSentence>{...}

compareTo() implementation:

@Override
public int compareTo(FinalSentence o) {
    if (this == o) {
        return 0;
    }
    if (this.score > o.score) {
        return 1;
    }
    if (this.score < o.score) {
        return -1;
    }
    return 0;
}

this is the exception:

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
at java.util.ComparableTimSort.mergeHi(Unknown Source)
at java.util.ComparableTimSort.mergeAt(Unknown Source)
at java.util.ComparableTimSort.mergeCollapse(Unknown Source)
at java.util.ComparableTimSort.sort(Unknown Source)
at java.util.ComparableTimSort.sort(Unknown Source)
at java.util.Arrays.sort(Unknown Source)
at java.util.Collections.sort(Unknown Source)
at feature.finalRepresentation.Summarizer.summarize(Summarizer.java:30)
at driver.Driver.main(Driver.java:114)

for a small list (less than 50 elements) it works. for a large list (it's supposed to work with those as well) it throws this exception. The instance type of the List is ArrayList, not that it should matter.

I have no idea how to get to the bottom of this. The list is full, the elements are of the same type (no polymorphism there) and yet I get this weird exception for large lists.

Any ideas?

Thanks ahead!!!

Answer 1

According to the OP's comment, my suggestion of using

Double.compare(score, o.score)

fixed the issue. My guess is that there was either a problem with ±0s or NaNs. In fact, if you look at the source of Double.compare(), you will find that it's slightly more complicated than you might think, and treats these cases specifically:

958    public static int compare(double d1, double d2) {
959        if (d1 < d2)
960            return -1;           // Neither val is NaN, thisVal is smaller
961        if (d1 > d2)
962            return 1;            // Neither val is NaN, thisVal is larger
963
964        long thisBits = Double.doubleToLongBits(d1);
965        long anotherBits = Double.doubleToLongBits(d2);
966
967        return (thisBits == anotherBits ?  0 : // Values are equal
968                (thisBits < anotherBits ? -1 : // (-0.0, 0.0) or (!NaN, NaN)
969                 1));                          // (0.0, -0.0) or (NaN, !NaN)
970    }

(source)

Moral is: be careful when comparing doubles! :)

---

Reference:

• Double.compare()

Answer 2

It could happen if you break the transitivity rule. If A>B and B>C, then C>A breaks the contract