1. class MergeSort<E extends Comparable<E>> implements Sorter<E> {
  2.  
  3. private E[] array, array2;
  4.  
  5. public void sort(E[] array) {
  6. this.array = array;
  7. array2 = array.clone();
  8. sort(0, array.length - 1);
  9. }
  10.  
  11. private void sort(int left, int right) {
  12. if (left >= right)
  13. return;
  14.  
  15. int middle = (left + right) / 2;
  16. sort(left, middle);
  17. sort(middle + 1, right);
  18.  
  19. int i = left;
  20. int a = left;
  21. int b = middle + 1;
  22. while (a <= middle || b <= right) {
  23. // If both a <= middle and b <= right
  24. // copy the smaller of array[a] or array[b] to array2[i]
  25. // Otherwise just copy the remaining elements to array2
  26. if (a <= middle && b <= right) {
  27. if (array[a].compareTo(array[b]) < 0) {
  28. array2[i] = array[a];
  29. a++;
  30. } else {
  31. array2[i] = array[b];
  32. b++;
  33. }
  34. i++;
  35.  
  36. } else {
  37. if (a > middle) {
  38. System.arraycopy(array, b, array2, i, array.length - b - 1);
  39. } else {
  40. System.arraycopy(array, a, array2, i, middle - a + 1);
  41. }
  42. break;
  43. }
  44. }
  45.  
  46. System.arraycopy(array2, left, array, left, right - left + 1);
  47. }