Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Nov 4th, 2013  |  syntax: None  |  size: 1.09 KB  |  views: 47  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  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.         }