class MergeSort<E extends Comparable<E>> implements Sorter<E> {
private E[] array, array2;
public void sort(E[] array) {
this.array = array;
array2 = array.clone();
sort(0, array.length - 1);
}
private void sort(int left, int right) {
if (left >= right)
return;
int middle = (left + right) / 2;
sort(left, middle);
sort(middle + 1, right);
int i = left;
int a = left;
int b = middle + 1;
while (a <= middle || b <= right) {
// If both a <= middle and b <= right
// copy the smaller of array[a] or array[b] to array2[i]
// Otherwise just copy the remaining elements to array2
if (a <= middle && b <= right) {
if (array[a].compareTo(array[b]) < 0) {
array2[i] = array[a];
a++;
} else {
array2[i] = array[b];
b++;
}
i++;
} else {
if (a > middle) {
System.arraycopy(array, b, array2, i, array.length - b - 1);
} else {
System.arraycopy(array, a, array2, i, middle - a + 1);
}
break;
}
}
System.arraycopy(array2, left, array, left, right - left + 1);
}