class MergeSort>

implements Sorter {

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

// If both a

// copy the smaller of array[a] or array[b] to array2[i]

// Otherwise just copy the remaining elements to array2

}

System.arraycopy(array2, left, array, left, right - left + 1);

}

}

4 Ditto Mergesort