Compared To What?

I recently ran into an issue with the venerable Collections#sort(List) method. The List that I was sorting had an unexpected null element, which resulted in a NullPointerException during the sort. My first inclination was to change the compareTo() method to handle nulls. This didn't work, however, because of line 1157 of the Arrays#mergeSort(Object[], Object[], int, int, int) method.

1153           // Insertion sort on smallest arrays
1154           if (length < INSERTIONSORT_THRESHOLD) {
1155               for (int i=low; ilow &&
1157                            ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
1158                       swap(dest, j, j-1);
1159               return;
1160           }

The method doesn't do any null checking, so if the object on the left side of the comparison is null, a NullPointerException will ensue. Punting on this concern was probably a good idea, since the whole idea of allowing null objects in a List is controversial, nevermind figuring out where to put them in the sort order. It would have been nice if there was more information about this in the API documentation. Effective Java mentions that the compareTo() method of a Comparable type should throw a NullPointerException if it receives a null object in Item 11, but the API docs for Arrays and Comparable don't say anything about how nulls are handled.

I looked further into the Arrays class and noticed that the Comparator and Comparator-less sort methods are essentially line-by-line copies of each other, except the Comparator version uses the Comparator object to perform the comparison. I would have expected them to use the same underlying code, perhaps by creating an anonymous Comparator instance that delegates to the compareTo() method, but I digress...

I finally solved the problem by creating a Comparator that can properly handle null objects. If you ever face this problem and you're using the Google Collections library, you can use the Comparators#nullLeastOrder() or Comparators#nullGreatestOrder() methods to obtain a Comparator that can handle null objects gracefully.