Comparator Sorting

Question

Please find the code below:

Collections.sort(longList, new Comparator<Long>() {
                        public int compare(long m1, long m2) {                          
                                return (int) (m2 - m1);                             
                            }

For some input it throws the following error:

 java.lang.IllegalArgumentException: Comparison method violates its general contract!
        at java.util.TimSort.mergeLo(TimSort.java:763)
        at java.util.TimSort.mergeAt(TimSort.java:499)
        at java.util.TimSort.mergeForceCollapse(TimSort.java:442)
        at java.util.TimSort.sort(TimSort.java:239)
        at java.util.TimSort.sort(TimSort.java:189)
        at java.util.Arrays.sort(Arrays.java:867)
        at java.util.Collections.sort(Collections.java:229)

Please help!

Answer 1

I'm assuming you have a typo in the question and the actual signature of the compare method is int compare(Long m1, Long m2), or your code wouldn't pass compilation at all, which is not the issue you describe.

The actual issue is that you are trying to compare two longs by returning the difference between them cast to int. This may give you incorrect results when the difference is not within the range of the int type. You can use return m2.compareTo(m1) instead (or return m2 < m1 ? -1 : m2 > m1 ? 1 : 0 if you don't want to rely on Long's compareTo implementation).

Answer 2

Doing this:

    Comparator<Long> d = new Comparator<Long>() {
        public int compare(long m1, long m2) {
            return (int) (m2 - m1);
        }
    };

is the same as NOT implementing the abstract method in the comparator interface

public int compare(T a1, T a2);

so your code is not compiling

you should use (is java8) the method reference

Comparator<Long> d = Long::compare;

but what is wrong whit this: (int) (m2 - m1); may you be asking yourself...

well you are forcing a cast of 2 a long into a integer, so that result can be a very negative Long or a positive integer

check this example to clarify:

    long b = 1000_000_000_000_000L;
    long a = 100L;
    System.out.println(a - b);
    System.out.println((int) (a - b));

the result is as long

-999999999999900

as int

1530495076

which is definitely breaking the comparation results

Answer 3

    List<Long> list = Arrays.asList(3L, 2L, 1L);

    list.sort(new Comparator<Long>() {
        @Override
        public int compare(Long o1, Long o2) {
            return o1.compareTo(o2);
        }
    });

    System.out.println(list);

OR:

    List<Long> list = Arrays.asList(3L, 2L, 1L);
    list.sort(Long::compareTo);
    System.out.println(list);

Answer 4

There are two things worth mentioning here:

• you always use @Override when you write down a method of which you think should override something. Then the compiler can tell you when you got something wrong (as in your case, where the signature expects Long, but you used long)
• Avoid re-inventing the wheel, even when it is just for reversing the comparison.

In other words: instead of doing

int compare(Long l1, long l2) {
  return l2 - l1;

you could do:

  return l2.compareTo(l1);

instead. That is just easier to read; and performance is basically the same.