A sorting bug
Tags: java, bug, sorting
Published: 2020-07-26 15:30:53

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](https://www.scala-lang.org/api/current/scala/util/Sorting$.html) provides [Quick Sort](https://en.wikipedia.org/wiki/Quicksort)
* [Ruby](https://8thlight.com/blog/will-warner/2013/03/26/stable-sorting-in-ruby.html) offers Quick Sort as well
* [Python](https://github.com/python/cpython/blob/master/Objects/listobject.c) uses [Timsort](https://en.wikipedia.org/wiki/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.

![Java Sorting API](https://dev-to-uploads.s3.amazonaws.com/i/tl18rzc1tqgntfstb6r2.png)

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](https://blog.frankel.ch/default-methods-java-8/) 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](https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/Comparator.html#compare(T,T))

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:

```java
(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:

```java
(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](https://blog.frankel.ch/sorting-bug) on July 26<sup>th</sup>, 2020_