A sorting bug

Lately, I succumbed to nostalgia, and agreed to do some consulting for a customer. The job was to audit the internal quality of an application, and finally to make recommandations to improve the code base and reimburse the technical debt. While parsing the source code, I couldn't help but notice a bug in the implementation of a Comparator.

This post is to understand how sorting works in Java, what is a Comparator, and how to prevent fellow developers to fall into the same trap. Even if it's obvious to experienced developers, I do believe it's a good refresher nonetheless.

Context

Most languages offer an out-of-the-box implementation of a (or more) sorting algorithm.

• Scala provides Quick Sort
• Ruby offers Quick Sort as well
• Python uses Timsort
• Java borrowed its implementation from Python
• etc.

Providing shared utilities as part of the language stack (or a library) has two main benefits:

1. Using an API is much more cost-effective than every developer implementing it over and over again
2. A significant portion of developers - including myself - would probably have bugs in their first iteration. Sharing code means it's battle-tested by a lot of other developers.

Java's sorting API

Yet, even though the algorithm is provided, it relies on some properties of the underlying to-be-sorted elements. In Java, and I believe in every strongly statically typed language, this is enforced by the API through types.

Note that in recent Java versions, the sorting algorithm has been moved from Collections.sort() to the List.sort() method. The latter is a default method. For more information on this move, please check my previous post on this specific subject.

The List.sort() method accepts a Comparator argument. If it's null, the algorithm will sort according to the natural order of elements, which is the contract of Comparable. If it's not, it will sort according to the Comparator argument. Fundamentally, the contract of Comparator.compare() is the following:

Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

-- JavaDoc

To sum it up, it returns o1 minus o2: it's up to the developer to define the implementation of the minus operation in the context of type T. With that, Timsort is able to compare elements in pairs and work its magic.

The bug

Now, the implementation I stumbled upon was the following:

(foo1, foo2) -> {
  if (foo1 == null || foo2 == null) {       // 1
    return 0;
  } else {
    return foo1.compareTo(foo2);            // 2
  }
}

1. Take care of null values
2. Compare using a specific method. I'm using compareTo() as a simple illustration

Can you spot the issue?

It works as expected until null values are part of the List to be sorted. During sorting, the null value will be compared to other Foo values: since it returns 0 in that case, it will be considered equal to the other value, even when the latter is not null! In short, it means null values won't be re-ordered, and will keep their index in the collection.

The fix

I believe the fix is straightforward:

(foo1, foo2) -> {
  if (foo1 == null && foo2 == null) return 0;  // 1
  if (foo1 == null)                 return -1; // 1
  if (foo2 == null)                 return 1;  // 1
  return foo1.compareTo(foo2);
}

1. The fix

By returning -1 unless both values are null, null values are always treated as being less than any other value. Similarly, one could decide to return 1 to move null values at the end of the sorted list.

All in all, the result of the sorting process needs to be the same regardless of the initial order of the elements. To achieve that, it's necessary to handle null values in a consistent way.

Originally published at A Java Geek on July 26^th, 2020