IllegalArgumentException in ArrayList.sort()-method [duplicate]

Question

I got following exception and I don't quite unterstand why:

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

at java.util.TimSort.mergeLo(TimSort.java:777) at java.util.TimSort.mergeAt(TimSort.java:514) 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:1454)

I wrote following JUnit test to verify the behavior:

@Test
public void testComparator() {
    List<Boolean> item = new ArrayList<>();

    item.add(true);
    for (int i = 0; i < 1000000; i++) {
        item.add(false);
    }

    while(true) {
        System.out.println("Sorting");
        Collections.shuffle(item);

        item.sort((lineItem1, lineItem2) -> {
            if (lineItem1 && lineItem2) {
                return 0;
            } else if (!lineItem1) {
                return 1; 
            } else if (!lineItem2 ) {
                return -1;
            } 

            return 0;
        });
    }
}

If I swap the return 1 and return -1, it suddenly works without exception. But why? This should only change the sorting order and not break the whole comparator.

What am I missing?

Answer 1

You comparator violates the contract, as when both arguments are false, it will return 1 due to the statement if (!lineItem1) { return 1; }….

Generally, there is no guaranty that TimSort will spot incorrect comparators, it doesn’t actively try to find contract violations, it just detects some cases as a side effect of the algorithm.

What you actually want to to is

item.sort((lineItem1, lineItem2) -> {
    if (lineItem1.equals(lineItem2)) {
        return 0;
    } else if (!lineItem1) {
        return 1; 
    } else {
        return -1;
    }
});

though you could achieve the same just using

item.sort((lineItem1, lineItem2) -> lineItem1^lineItem2? lineItem1? -1: 1: 0);

or even simpler

item.sort(Comparator.reverseOrder());