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

Question

java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.util.TimSort.mergeLo(TimSort.java:747)
    at java.util.TimSort.mergeAt(TimSort.java:483)
    at java.util.TimSort.mergeCollapse(TimSort.java:410)
    at java.util.TimSort.sort(TimSort.java:214)
    at java.util.TimSort.sort(TimSort.java:173)
    at java.util.Arrays.sort(Arrays.java:659)
    at java.util.Collections.sort(Collections.java:217)

I am sorting a collection based on the following comparator.

public static Comparator<MyClass> CMP_TIME_DESC = new Comparator<MyClass>() {
    @Override
    public int compare(MyClass o1, MyClass o2) {
        return o2.getOrderSendTime().compareTo(o1.getOrderSendTime());
    }
};

The values are always non-null. And the getOrderSendTime() object is of the java.util.Date class.

I understand that this is a transitivity inconsistency, and I would assume a class like this would not have such issues. I searched for open issues, but did not find any on the topic.

Any ideas?

Answer 1

Your issue is related to this one: Sort algorithm changes in Java 7

It happens because the default sort algorithm has changed from MergeSort to TimSort.

One workaround is to add -Djava.util.Arrays.useLegacyMergeSort=true to the JVM environment.

The best option is to conform to the comparison general contract but I think you didn't provide enough information in your question for this.

Answer 2

I had this same exception, and it happened when I had java.util.Date and java.sql.Timestamp objects in the same list/array when being sorted, running on Java8. (This mix was due to some objects being loaded from database records with the Timestamp data type, and others being created manually, and the objects having only a Date object in them.)

The exception also doesn't happen every time you sort the same data set, and it seems that there also have to be at least 32 of these mixed objects in the array for it to occur.

If I use the legacy sort algorithm, this also doesn't occur (see how in Ortomala Lokni's answer).

This also doesn't happen if you use only java.util.Date objects or only java.sql.Timestamp objects in the array.

So, the issue seems to be TimSort combined with the compareTo methods in java.util.Date and java.sql.Timestamp.

However, it didn't pay for me to research why this is happening since it is fixed in Java 9!

As a workaround until Java9 is released and we can get our systems updated, we have manually implemented a Comparator that only uses getTime(). This seems to work fine.

Here is code that can be used to reproduce the issue:

import java.sql.Timestamp;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Date;
import java.util.List;
import org.junit.Test;

public class TimSortDateAndTimestampTest {

    // the same test data with all Dates, all Timestamps, all Strings or all Longs does NOT fail.
    // only fails with mixed Timestamp and Date objects
    @Test
    public void testSortWithTimestampsAndDatesFails() throws Exception {
        List<Date> dates = new ArrayList<>();
        dates.add(new Timestamp(1498621254602L));
        dates.add(new Timestamp(1498621254603L));
        dates.add(new Timestamp(1498621254603L));
        dates.add(new Timestamp(1498621254604L));
        dates.add(new Timestamp(1498621254604L));
        dates.add(new Timestamp(1498621254605L));
        dates.add(new Timestamp(1498621254605L));
        dates.add(new Timestamp(1498621254605L));
        dates.add(new Timestamp(1498621254605L));
        dates.add(new Timestamp(1498621254606L));
        dates.add(new Timestamp(1498621254607L));
        dates.add(new Date(1498621254605L));
        dates.add(new Timestamp(1498621254607L));
        dates.add(new Timestamp(1498621254609L));
        dates.add(new Date(1498621254603L));
        dates.add(new Date(1498621254604L));
        dates.add(new Date(1498621254605L));
        dates.add(new Date(1498621254605L));
        dates.add(new Date(1498621254607L));
        dates.add(new Timestamp(1498621254607L));
        dates.add(new Date(1498621254608L));
        dates.add(new Timestamp(1498621254608L));
        dates.add(new Date(1498621254611L));
        dates.add(new Timestamp(1498621254612L));
        dates.add(new Timestamp(1498621254613L));
        dates.add(new Date(1498621254607L));
        dates.add(new Timestamp(1498621254607L));
        dates.add(new Timestamp(1498621254608L));
        dates.add(new Timestamp(1498621254609L));
        dates.add(new Timestamp(1498621254611L));
        dates.add(new Date(1498621254603L));
        dates.add(new Date(1498621254606L));

        for (int i = 0; i < 200; i++) {
            Collections.shuffle(dates);
            Collections.sort(dates);
        }
    }
}

Edit: I have removed the exception expectation so you can SEE it throwing when run.