Generics and sorting in Java

Question

Suppose you write a static function in Java to sort an array, much like Arrays.sort(). The problem with Arrays.sort() is that it receives an array of Object, and throws a ClassCastException if its elements don't implement Comparable.

So you want your function to receive as an argument an array of a subtype of Comparable. Something like that could work:

static <T extends Comparable> void sort(T[] array);

The problem with that signature is that you can still pass an array of Comparables with Integers and Strings for instance, which would cause a Runtime exception.

So, how can you create a function that will receive only an array whose elements implement Comparable and have all the same type (eg. Integer, String, etc?)

Answer 1

Use

static <T extends Comparable<? super T>> sort(T[] array);

which is the most general specification to accomplish the task. Basically, it asserts, that T is a type which can be compared to itself.

Answer 2

Dirk's answer is the best you can get, but Google Collections used exactly as you wrote to avoid bug in javac:

From: http://code.google.com/p/google-collections/wiki/Faq

Why do you use the type <E extends Comparable> in various APIs, which is not "fully
generified"? Shouldn't it be <E extends Comparable<?>>, <E extends Comparable<E>> 
or <E extends Comparable<? super E>>?

The last suggestion is the correct one, as explained in Effective Java. However, 
we will be using <E extends Comparable<E>> on parameterless methods in order to 
work around a hideous javac bug. This will cause you problems when you use a very 
unusual type like java.sql.Timestamp which is comparable to a supertype. 
(Needs more explanation.)

Now it's up to you...

Answer 3

In the post-1.5 Java world, reference arrays are just low-level implementation details. Prefer, collections.

If you are interested in reference arrays, for some peculiar reason, you will be aware they really don't get on with generics. You can't (reasonably) have an array of a generic type, such as Comparable<String>. That means that if Arrays.sort was genericised in a similar way to Collections.sort it would be over constrained.

Because of the peculiarity of array typing, if you did want to over-constrain types, I think sort can be written more simply than Collections.sort without sacrificing anything significant.

public static <T extends Comparable<T>> sort(T[] array)

If you want binary compatibility with pre-generics, then you will need a slight hack to get back to the Object[] signature, in a similar way to the likes of Collections.min.

public static <T extends Object & Comparable<T>> sort(T[] array)