Casting array of objects to array of comparable

Question

I've encountered a problem while doing a homework for online algorithms class. Casting Object[] to T[] where T is Comparable raises a run-time exception

public  static <T extends Comparable<? super T>> void mergeSort(T[] xs) {
    T[] aux = (T[]) new Object[xs.length];
    mergeSort(xs, aux, 0, xs.length);
}

I could rewrite it in C# which doesn't have any problems with creating generic arrays but I'd rather learn how to deal with this in Java.

Answer 1

If you're getting a runtime exception, it means that the objects you tried to cast don't acutally have that type. Language doesn't have anything to do with it. There's probably a bug in your code.

Edit: It sounds like you are confused by how Java's type system works. In C#, generics actually represent different types at runtime. In Java, generic types don't exist at runtime. They are only a convenience to enable better compile time type checking. During compilation, generics are replaced by a real type in a process known as type erasure.

Normally, the erasure of a generic type is Object, but since you provided an upper bound for T, it is converted to that bound, Comparable. Therefore, after erasure, your code looks like this.

Comparable[] aux = (Comparable[]) new Object[xs.length];

In otherwords, you're creating an array of type Object[] and immediately trying to cast it to type Comparable[]. Since Object doesn't implement Comparable, the types are incompatible, so you get a runtime exception. You can fix this by creating an array of Comparables instead.

public  static <T extends Comparable<? super T>> void mergeSort(T[] xs) {
    T[] aux = (T[]) new Comparable[xs.length];
    mergeSort(xs, aux, 0, xs.length);
}

Answer 2

Try this:

public  static <T extends Comparable<? super T>> void mergeSort(T[] xs) {
    T[] aux = (T[])java.lang.reflect.Array.newInstance(xs.getClass().getComponentType(), xs.length);
    mergeSort(xs, aux, 0, xs.length);
}