Comparison method violates its general contract! (elements duplicated in collection during sort)

Question

I know there are many topics with same subject, but this case seems to me a bit different and not well-documented in javadocs. Here is the code:

Random random = new Random(0);

var list = new ArrayList<>();
for (int i = 0; i < 60; i++) {
    list.add(random.nextInt());
}

list.sort((x, y) -> {
    int sum = list.stream().reduce(0, Integer::sum);

    System.out.println(sum);

    return Integer.compare(x + sum, y + sum);
});

The result is exception:

-1303811196
-1303811196
.....
-1303811196
-1303811196
-1303811196
-1364558868
-1569607140
-1836181454
-2014724660
-2023409163
-2094470032
-2128134715
2107317277
2107317277
Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.base/java.util.TimSort.mergeLo(TimSort.java:781)
    at java.base/java.util.TimSort.mergeAt(TimSort.java:518)
    at java.base/java.util.TimSort.mergeCollapse(TimSort.java:448)
    at java.base/java.util.TimSort.sort(TimSort.java:245)
    at java.base/java.util.Arrays.sort(Arrays.java:1516)
    at java.base/java.util.ArrayList.sort(ArrayList.java:1717)
    at HomeWork6_4.Company.main(Company.java:131)

So it seems like, it's not possible to rely on collection during sorting, because its in dirty state. Is that behavior documented somewhere?

Answer 1

Let us debug by logging what the Comparator is doing internally. For that, I am adding a special logging method to track the results of the comparator. Please check the code below

public static void main(String[] args) {
    Random random = new Random(0);
    
    var list = new ArrayList<Integer>();

    for (int i = 0; i < 60; i++) {
        list.add(random.nextInt());
    }
    list.sort(logging((x, y) -> {
        int sum = list.stream().reduce(0, Integer::sum);
        return Integer.compare(x + sum, y + sum);
    }));
}

public static Comparator<Integer> logging(Comparator<Integer> c) {
    return (Integer a, Integer b)-> {
        int r = c.compare(a, b);
        System.err.printf("%7d  %7d => %2d%n", a, b, r);
        return r;
    };
}

The behaviour of Comparator for two inputs (T a, T b) is following

(i) returns  less than 0 ,  means a<b
(ii)returns 0 , means a==b
(iii)return greater than 0 , means a>b

If any comparator doesn't satisfy these rules, we say the comparator is broken. Now let's pay close attention to what the comparator is logging

-723955400  -1155484576 => -1  // broken (a>b but comparator Integer.compare(a+sum,b+sum) returned less than 0)
1033096058  -723955400 =>  1   // broken 
1033096058  -1155484576 => -1
1033096058  -723955400 =>  1
-1690734402  1033096058 =>  1. // broken 

This shows that the specific comparator you used Integer.compare(a+sum, b+sum) has overflown and resulted in the inconsistent result when you apply against the list elements. When such a broken comparator is used sort(c) throws such Exception.