Sorting Collections in Java

This article was originally published on the Encodo Blogs. Browse on over to see more!

One of the features we expect from a collections library is sorting. You should be able to use generic library mechanisms to sort a list of any kind of element. Most libraries include a generic sort function, to which a comparison functor (object or function pointer) is passed. This functor is called repeatedly on pairs of elements until the list is sorted.

Let’s define the simple class we’ll use in the ensuing examples.

class A {
  String fileName;
  
  function getFileName() {
    return fileName;
  }
}

Now, let’s sort a List<A>. Is there a sort function on the list object itself? No. Why not? Legacy reasons. In order to avoid breaking existing code, Java has not made any changes to the List interface. Ever. Therefore, you will have to search for any new functionality in the global function unit masquerading as a class[1] called Collections.

There are two sorting functions defined in this class, shown below:

public static <T extends Comparable<? super T>> void sort(List<T> list);
public static <T> void sort(List<T> list, Comparator<? super T> c);

Neither one of these is exactly easy on the eyes and both include the wildcard (?) operator in their definitions. The first version accepts a List<T> only if T extends Comparable directly or a generic instantiation of Comparable which takes T or a superclass as a generic parameter. The second version takes a List<T> and a Comparator instantiated with T or a supertype.

With our simple class A above, it would be pretty easy to implement the interface to give the class a standard ordering. Naively, we might add the following:

class A implements Comparable {
  String fileName;
  
  function getFileName() {
    return fileName;
  }

  public int compareTo(Object _o) {
    return getFileName().compareTo((A) _o.getFileName());
  }
}

The compiler seems pretty happy with it, but actually calling sort() with a List<A> results in a warning:

If you’re using Eclipse, your “Quick-Fix” trigger finger is probably getting mighty itchy right now, but let’s avoid simply adding a @Suppress directive above this function and try to find out why the class compiles, but the function call has a problem.

A quick search through Google Groups turns up Collections.sort() in Java 5, which reminds us that “[t]he Comparable interface takes a generic parameter”. Adding in the generic argument (as shown below) fixed the problem and gets rid of the warning.

class A implements Comparable<A> {
  …

  public int compareTo(A _o) {
    return getFileName().compareTo(_o.getFileName());
  }
}

On top of that, the generic version of Comparable allows us to declare a type-specific compareTo function and get rid of the ugly cast. All’s well that ends well, but it would be much nicer if the compiler could tell us that we are misusing Comparable than to have to find out from some guy in a newsgroup.

Using Java 1.5