IllegalArgumentException in ArrayList.sort()-method

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?

Checked [this](https://stackoverflow.com/questions/8327514/comparison-method-violates-its-general-contract) already? — pirho, Jan 22 '18 at 15:54
Does your code violate this rule? `The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y. (This implies that compare(x, y) must throw an exception if and only if compare(y, x) throws an exception.)` from [doc](https://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html#compare-T-T-) — Gab, Jan 22 '18 at 15:55
You are violating the contract because you currently return 1 when lineItem1 is false regardless of what value lineItem2 has. But if both are false you need to return 0. — OH GOD SPIDERS, Jan 22 '18 at 15:57
@doc: I would say, no it doesn't violate it. compare(true, false) = -1, compare(false, true) = 1 and sgn(-1) == sgn(1) — C. Koenig, Jan 22 '18 at 15:58
@C.Koenig compare(A=false, B=false) returns 1 but compare(B=false, A=false) also returns 1. So which one would be sorted higher in that case: A or B? Both are bigger than the other after all. — OH GOD SPIDERS, Jan 22 '18 at 16:02
If I may be allowed to plug my talk on this subject.... Part 1: https://youtu.be/Enwbh6wpnYs ... Part 2: https://youtu.be/bvnmbRo7a1Y — Stuart Marks, Jan 22 '18 at 18:50

score 7 · Accepted Answer · answered Jan 22 '18 at 16:04

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());

So its basically luck, that no exception is thrown, when I exchange the ordering? — C. Koenig, Jan 22 '18 at 17:11
@C.Koenig exactly. Before the introduction of the TimSort algorithm, such problems were never reported, you could even have the luck to see the desired result order, or rather, bad luck as you didn’t noticed the still existing problem in the code… — Holger, Jan 22 '18 at 17:15

IllegalArgumentException in ArrayList.sort()-method

1 Answers1