Java unexpected IllegalArgumentException in sorting with Math.abs(diff)

Question

I have some behaviour I didn't expect concerning when sorting a list of Doubles. The goal I have is to sort a list of doubles, but when the two doubles are near each other, then I don't care about their order (in reality, I use an Entry<> with a Double as the value, and when the two Double values are close, I sort on something else.

Here is a sample that will throw an IllegalArgumentException:

public static void main(String[] args) {
    final float probabilitySortMargin = 0.2f;
    Comparator<Double> comp = new Comparator<Double>() {
        @Override
        public int compare(Double o1, Double o2) {
            // sort on probability first
            double diff = Math.abs(o1 - o2);
            if(diff > probabilitySortMargin)
                // difference is more than desired range, sort descending
                return Double.compare(o2 , o1);
            return 0;
        }
    };

    ArrayList<Double> vals = new ArrayList<>();
    Random r = new Random(0);
    for(int i=0;i<1000;i++)
        vals.add(r.nextDouble());

    for(int i=0;i<vals.size();i++)
        for(int j=0;j<vals.size();j++)
            if(comp.compare(vals.get(i), vals.get(j)) != -1 * comp.compare(vals.get(j), vals.get(i)))
                System.out.println("Comparison failed");

    Collections.sort(vals, comp);
}

which results in

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.util.TimSort.mergeHi(TimSort.java:899)
    at java.util.TimSort.mergeAt(TimSort.java:516)
    at java.util.TimSort.mergeCollapse(TimSort.java:441)
    at java.util.TimSort.sort(TimSort.java:245)
    at java.util.Arrays.sort(Arrays.java:1512)
    at java.util.ArrayList.sort(ArrayList.java:1462)
    at java.util.Collections.sort(Collections.java:175)
    at some.package.Sample.main(Sample.java:10)

Why is this happening? Even weirder, the error message "Comparison failed" is NOT printed.

that's because the comparison is not executed, because the comparison you try to do is not valid for the contract to which the comparator is bound. have you read the stacktrace you pasted here? find out what's wrong with either the comparator, or with the parameter you pass, and update your code accordingly — Stultuske, Nov 06 '18 at 12:41
Possible duplicate of [Java error: Comparison method violates its general contract](https://stackoverflow.com/questions/11441666/java-error-comparison-method-violates-its-general-contract) — Karol Dowbecki, Nov 06 '18 at 12:43

Eran · Accepted Answer · 2018-11-06T12:47:03.823

3

Your compare method does violate the contract of the Comparator interface.

the implementor must ensure that compare(x, y)==0implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z.

compare(0.1,0.2) == 0, but sgn(compare(0.1,0.35)) != sgn(compare (0.2,0.35))

"Comparison failed" is never printed because your method doesn't violate the sgn(compare(x, y)) ==-sgn(compare(y, x)) requirement.

edited Nov 06 '18 at 12:47

answered Nov 06 '18 at 12:44

Eran

387,369
54
702
768

Java unexpected IllegalArgumentException in sorting with Math.abs(diff)

1 Answers1