Understand comparison method when sorting a collection

Question

I have the following piece of code to sort a collection of Items that have a label property:

Collections.sort(myList, new Comparator<ListItem>() {
            @Override
            public int compare(ListItem lhs, ListItem rhs) {
                Crashlytics.log(Log.DEBUG, TAG, "lhs.getLabel(): " + lhs.getLabel() + " | rhs.getLabel(): " + rhs.getLabel());
                if (lhs.getLabel() == null || rhs.getLabel() == null) {
                    return 0;
                }
                return lhs.getLabel().compareTo(rhs.getLabel());
            }
        });

I have some crash reports with the following stacktrace:

Caused by 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.mergeForceCollapse(TimSort.java:457)
       at java.util.TimSort.sort(TimSort.java:254)
       at java.util.Arrays.sort(Arrays.java:1498)
       at java.util.ArrayList.sort(ArrayList.java:1470)
       at java.util.Collections.sort(Collections.java:201)
       at uk.co.aquanetix.activities.MyActivity.onCreate(MyActivity.java:59)
       at android.app.Activity.performCreate(Activity.java:7183)
       at android.app.Instrumentation.callActivityOnCreate(Instrumentation.java:1220)
       at android.app.ActivityThread.performLaunchActivity(ActivityThread.java:2910)
       at android.app.ActivityThread.handleLaunchActivity(ActivityThread.java:3032)
       at android.app.ActivityThread.-wrap11(Unknown Source)
       at android.app.ActivityThread$H.handleMessage(ActivityThread.java:1696)
       at android.os.Handler.dispatchMessage(Handler.java:105)
       at android.os.Looper.loop(Looper.java:164)
       at android.app.ActivityThread.main(ActivityThread.java:6944)
       at java.lang.reflect.Method.invoke(Method.java)
       at com.android.internal.os.Zygote$MethodAndArgsCaller.run(Zygote.java:327)
       at com.android.internal.os.ZygoteInit.main(ZygoteInit.java:1374)

I understand that this is related to the fact that the comparator method is not transitive, as explained here.

My problem is that I am not able to reproduce it. It only happens in some specific situation that I can't figure out.

As you can see, I am sending the label values to Crashlytics, so these are the values that were sent when the crash happened.

0 | 1545921010869 | D/MyActivity lhs.getLabel(): 14:49:22 | rhs.getLabel(): 13:21:22
1 | 1545921010870 | D/MyActivity lhs.getLabel(): 13:25:41 | rhs.getLabel(): 14:49:22
2 | 1545921010870 | D/MyActivity lhs.getLabel(): 13:25:41 | rhs.getLabel(): 14:49:22
3 | 1545921010870 | D/MyActivity lhs.getLabel(): 13:25:41 | rhs.getLabel(): 13:21:22
4 | 1545921010870 | D/MyActivity lhs.getLabel(): 14:53:26 | rhs.getLabel(): 13:25:41
5 | 1545921010870 | D/MyActivity lhs.getLabel(): 14:53:26 | rhs.getLabel(): 14:49:22
6 | 1545921010870 | D/MyActivity lhs.getLabel():  | rhs.getLabel(): 14:49:22
7 | 1545921010870 | D/MyActivity lhs.getLabel():  | rhs.getLabel(): 13:25:41

I built a list with those values (plus some items with empty strings) but no luck in reproducing it in my device/emulators.

My questions are:

What could be the reason for not being able to reproduce using the same values?
Should the code be better without the if condition?

Your comparison function returns `0` when *either* of the objects is `null`. You probably want to decide whether `null` objects go at the beginning of the sorted-set or at the end and be consistent about it. — Christopher Schultz, Dec 28 '18 at 15:45
Comparison that you have will not be able to sort collection of labels `'a', 'b', null`, because `'a' < 'b'`, `'a' == null` and `'b' == null`, which makes it simultaneously `'a' < 'b'` and `'a' == 'b'` (because, `'a' == null == 'b'`), which makes no sense. — M. Prokhorov, Dec 28 '18 at 15:51

Mureinik · Accepted Answer · 2018-12-28T16:11:43.670

As you noted, this comparator isn't transitive. Consider three ListItems a, b and c with the labels "a", "b" and null, respectively. Using this comparator, compare(a, c) and compareTo(b, c) are both 0 since c.getLabel() is null, but compare(a, b) clearly isn't, thus breaking the rule of tansitivity.

To address this issue you can arbitrarily decide that ListItems with null labels will always go last (or first, for argument's sake. Just replace the 1s in the below code with -1s and vise-versa):

Collections.sort(myList, new Comparator<ListItem>() {
    @Override
    public int compare(ListItem lhs, ListItem rhs) {
        if (lhs.getLabel() == null) {
            if (rhs.getLabel() == null) {
                return 0;
            }
            return 1;
        }
        if (rhs.getLabel() == null) {
            return -1;
        }
        return lhs.getLabel().compareTo(rhs.getLabel());
    }
});

Note that if you're using Java 8 you can save a lot of this boilerplate code:

myList.sort(Comparator.comparing
            (ListItem::getLabel, Comparator.nullsLast(Comparator.naturalOrder())));

In the second case with ``nullLast`` you will still get ``NullPointerException`` — Schidu Luca, Dec 28 '18 at 15:54
@SchiduLuca oops, that was sloppy on my behalf. Edited and fixed. — Mureinik, Dec 28 '18 at 16:11

Understand comparison method when sorting a collection

1 Answers1