# Generic Array Initialization in MergeSort

Here’s my code, to implement a generic Mergesort.

```import java.util.Arrays;
public class MergeSort<T extends Comparable<T>> {
public static void main(String[] args) {
Integer[] int_arr = { 10, 20, 35, 40, 13, 42 };
MergeSort<Integer> IntegerSort = new MergeSort<>();
IntegerSort.Merge_Sort(int_arr, 0, int_arr.length - 1);
System.out.println(Arrays.toString(int_arr));
}
private void Merge_Sort(T[] A, int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
Merge_Sort(A, low, mid);
Merge_Sort(A, mid + 1, high);
Merge(A, low, mid, high);
}
}
private void Merge(T[] A, int low, int mid, int high) {
int n1 = mid - low + 1;
int n2 = high - mid;

T[] Left_sub = (T[]) new Object[n1];
T[] Right_sub = (T[]) new Object[n2];

for (int i = 0; i < n1; ++i) {
Left_sub[i] = A[low + i];
}
for (int j = 0; j < n2; ++j) {
Right_sub[j] = A[mid + j + 1];
}

int i = 0, j = 0;
for (int k = low; k < high; k++) {
if (less(Left_sub[i], Right_sub[j])) {
A[k] = Left_sub[i];
i = i + 1;
} else {
A[k] = Right_sub[j];
j = j + 1;
}
}
}
private boolean less(T v, T w) {
return v.compareTo(w) < 0;
}
}
```

I ran into this runtime error

```Exception in thread "main" java.lang.ClassCastException: class [Ljava.lang.Object; cannot be cast to class [Ljava.lang.Comparable; ([Ljava.lang.Object; and [Ljava.lang.Comparable; are in module java.base of loader 'bootstrap')
```

I am wrong at

```T[] Left_sub = (T[]) new Object[n1];
T[] Right_sub = (T[]) new Object[n2];
```

I tried other ways like `Arrays.copyofrange()`, `ArrayList<T>` Are there any other ways to initialize generic Arrays. Please suggest ways to perform the Merging process in the `Merge()` function.

To make a copy of range of the array, you should use `Arrays.copyRangeOf`:

```    T[] Left_sub = Arrays.copyOfRange(A, low, mid + 1);
T[] Right_sub = Arrays.copyOfRange(A, mid, high + 1);
```

Note these remarks:

• it is error prone to use the index of the last element of the slice as the `high` argument, you should use the index of the next element so the length of the slice is simply `high - low`.
• you can simplify the `merge` method and only copy the left portion of the slice since the elements in the right portion are not overwritten before they are copied.
• you should modify the loop to avoid reading non existent elements from the subarrays.

Here is a modified version:

```import java.util.Arrays;

public class MergeSort<T extends Comparable<T>> {
public static void main(String[] args) {
Integer[] int_arr = { 10, 20, 35, 40, 13, 42 };
MergeSort<Integer> IntegerSort = new MergeSort<>();
IntegerSort.Merge_Sort(int_arr, 0, int_arr.length);
System.out.println(Arrays.toString(int_arr));
}
private void Merge_Sort(T[] A, int low, int high) {
if (high - low >= 2) {
int mid = low + (high - low) / 2;  // avoid overfow or large values
Merge_Sort(A, low, mid);
Merge_Sort(A, mid, high);
Merge(A, low, mid, high);
}
}
private void Merge(T[] A, int low, int mid, int high) {
T[] Left_sub = Arrays.copyOfRange(A, low, mid);
int i = 0, j = mid, n1 = mid - low;
for (int k = low; k < high; k++) {
if (i < n1 && (j > high || Left_sub[i].compareTo(A[j]) <= 0)) {
A[k] = Left_sub[i++];
} else {
A[k] = A[j++];
}
}
}
}
```