Comparison method violates its general contract! Java7 Comparator

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:408)
    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)

Can someone explain why my comparator below sometimes throws the above exception.

Note: The id field in myObject is of type long.

Collections.sort(objectList, new Comparator<MyObject>() {

    @Override
    public int compare(final myObject myobject1, final MyObject myObject2) {

        return (int)(myObject1.getId() - myObject2.getId());

    }
});

Solution:

Based on the answer from @amit

return (int)(Long.compare(myObject1.getId(), myObject2.getId());

myObject should have an upper case M - Java code conventions are not optional and classes always start with a capital letter. — LionC, Aug 13 '15 at 09:05
@LionC apologies that was a typo. That's not what's causing the problem. — user5222688, Aug 13 '15 at 09:07
@Eran no, there is no possibility of nulls in the Collection — user5222688, Aug 13 '15 at 09:09
@LionC Code conventions are always optional; it is just not advisable to deviate from such a common convention. — Mark Rotteveel, Aug 13 '15 at 09:12
@MarkRotteveel **Everything** is optional. But there is a lot of things that people should never ever think of as optional. This is such a thing. — LionC, Aug 13 '15 at 09:15

score 4 · Accepted Answer · edited Jun 20 '20 at 09:12

4

You might encounter an integer overflow if the ID is relatively high integers in absolute values, which will cause VERY_HIGH_INT - VERY_LOW_INT to be a negative number. This is obviously wrong, and is breaking the contract of the comparator.

Use Integer.compare() (or similarly Long.compare(), Double.compare()...) rather than substracting numbers to avoid it.

EDIT:

Specifically here, the problem is still integer overflow, when casting a long value where its 32 LSbs are in range [2^31,2^32) from long to int, which causes it to be erroneously negative. Demo in ideone.

Solution is the same. Use Long.compare()

edited Jun 20 '20 at 09:12

Community

1
1

answered Aug 13 '15 at 09:08

amit

175,853
27
231
333

This shouldn't be an issue as long as only positive integer ids are used. And if you need more ids, I would consider using unsigned comparison, so that id `0` is always first. – kajacx Aug 13 '15 at 09:14
The id is based on System.currentTimeMillis() – user5222688 Aug 13 '15 at 09:16
@user5222688 See edit. The problem is still integer overflow. – amit Aug 13 '15 at 09:22
1

@kajacx It is still an issue when you case the long to int. see edit. – amit Aug 13 '15 at 09:23
@amit you are spot on. Thanks. – user5222688 Aug 13 '15 at 09:26

sjain · Answer 2 · 2015-08-13T09:23:46.263

0

Java 7 has changed the default sort algorithm from MergeSort to TimSort in the java.util.Arrays.sort method.

The sorting algorithm used by java.util.Arrays.sort and (indirectly) by java.util.Collections.sort has been replaced. The new sort implementation may throw an IllegalArgumentException if it detects a Comparable that violates the Comparable contract.

For backward compatibility and to restore the behavior from Java version 6, add new system property- java.util.Arrays.useLegacyMergeSort.

Refer the following link for details -

http://www.oracle.com/technetwork/java/javase/compatibility-417013.html#source

edited Aug 13 '15 at 09:23

answered Aug 13 '15 at 09:17

sjain

23,126
28
107
185

1

While informative, it does not answer the question. The OP is familiar with the contract, and doesn't really cares which sorting algorithm is involved. He cares why the contract in his comparator is broken, and this does not answer it. – amit Aug 13 '15 at 09:26

Comparison method violates its general contract! Java7 Comparator

2 Answers2