Creating a new array of a typical type using Array.newInstance ()

Question

For practice, I'm trying to implement a merge sort algorithm, but got stuck very quickly when trying to create an instance of a type array. I'm not quite sure if my plan will work, but now the interesting part (or disappointment, depending on when you ask me) is the second line in the merge () method. The newInstance () method should know which class it should initiate as, but even if arr1.getClass () compiles fine, it will not work at runtime.

public void mergeSort(T[] arr) { T[] merged = merge(Arrays.copyOfRange(arr, 0, arr.length/2), Arrays.copyOfRange(arr, arr.length/2+1, arr.length-1)); } @SuppressWarnings({"unchecked"}) public T[] merge(T[] arr1, T[] arr2) { // A new array of type T that will contain a merged version of arr1 and arr2 T[] merged = (T[]) Array.newInstance(arr1.getClass(), arr1.length+arr2.length); int i1 = 0, i2 = 0; for (int i = 0; i < arr1.length + arr2.length; i++) { if (arr1[i1].compareTo(arr2[i2]) < 0) { merged[i] = arr1[i1]; i1++; } else { merged[i] = arr2[i2]; i2++; } } return merged; } 

Error message:

 Exception in thread "main" java.lang.ClassCastException: [[Ljava.lang.String; cannot be cast to [Ljava.lang.Comparable; at sort.SortingAndSearching.merge(SortingAndSearching.java:94) at sort.SortingAndSearching.mergeSort(SortingAndSearching.java:84) at sort.SortingAndSearching.main(SortingAndSearching.java:19) 

Answer 1

I think I see the problem ... When you do Array.newInstance(...) , it takes on the type of the component (in your case, you want it to be a string). However, you pass an array class (arr1 is of type String [], and you do arr1.getClass() ). Instead do

 arr1.getClass().getComponentType() 

to get the String class from String[]

Per javadoc :

  static Object newInstance(Class<?> componentType, int[] dimensions) 

componentType - a class object representing the type type of the new array

Answer 2

I copied and pasted the code you gave, and it doesn't even compile. After making some corrections, I came to the following:

 public class Test { public <T extends Comparable> void mergeSort(T[] arr) { T[] merged = merge(Arrays.copyOfRange(arr, 0, arr.length / 2), Arrays.copyOfRange(arr, arr.length / 2 + 1, arr.length - 1)); } public <T extends Comparable> T[] merge(T[] arr1, T[] arr2) { // A new array of type T that will contain a merged version of arr1 and arr2 T[] merged = (T[]) Array.newInstance(arr1.getClass(), arr1.length + arr2.length); int i1 = 0, i2 = 0; for(int i = 0; i < arr1.length + arr2.length; i++) { if(arr1[i1].compareTo(arr2[i2]) < 0) { merged[i] = arr1[i1]; i1++; } else { merged[i] = arr2[i2]; i2++; } } return merged; } } 

Since you are using the compareTo method, you must tell the compiler that T implements this interface.