1. class MergeSorter  {
  2.  
  3.   @SuppressWarnings("unchecked")
  4.   <T extends Comparable<T>> void
  5.   mergeSort(T array[]) {
  6.  
  7.     // Permute the given array so that 0 <= i <= j < array.length
  8.     // implies a[i] <= a[j].
  9.  
  10.     final Comparable copy [] = new Comparable [array.length];
  11.  
  12.     if (mergeSort(array, 1, copy) != array)
  13.       for (int i = 0; i < array.length; i++)
  14.     array[i] = (T) copy[i];
  15.     }
  16.  
  17.  
  18.   private <T extends Comparable<T>> T []
  19.   mergeSort(T source[], int size, T target[]) {
  20.  
  21.     // Assuming source is a sequence of sorted element segments of at
  22.     // most the given size (that is, source[0..size - 1], source[size,
  23.     // 2*size - 1], ..., source[i*size..min(source.length, (i +
  24.     // 1)*size - 1], where i = floor(source.length/size)), store into
  25.     // target a permutation of the elements in source so that 0 <= i
  26.     // <= j < target.length implies target[i] <= target[j].
  27.  
  28.     final int n = source.length;
  29.  
  30.     if (size >= n)
  31.       return source;
  32.  
  33.     for (int i = 0; i < n; i += size*2)
  34.       merge(source, i, size, target);
  35.  
  36.     return mergeSort(target, size*2, source);
  37.     }
  38.  
  39.  
  40.   private <T extends Comparable<T>> void
  41.   merge(T source[], int left, int size, T target[]) {
  42.  
  43.     // Assuming source is a sequence of sorted element segments of at
  44.     // most the given size (that is, source[0..size - 1],
  45.     // source[size..2*size - 1], ...,
  46.     // source[i*size..min(source.length, (i + 1)*size - 1], where i =
  47.     // floor(source.length/size)), store into target the merger of
  48.     // adjacent segments from source (that is, target will be a
  49.     // sequence of sorted element segments of at most twice the given
  50.     // size).
  51.  
  52.     final int
  53.       n = source.length,
  54.       mid = Math.min(left + size, n),
  55.       right = Math.min(mid + size, n);
  56.     int
  57.       m = mid,
  58.       nextFree = left;
  59.  
  60.     while ((left < mid) && (m < right))
  61.       if (source[left].compareTo(source[m]) > 0)
  62.     target[nextFree++] = source[m++];
  63.       else
  64.     target[nextFree++] = source[left++];
  65.  
  66.     while (left < mid)
  67.       target[nextFree++] = source[left++];
  68.     while (m < right)
  69.       target[nextFree++] = source[m++];
  70.  
  71.     assert nextFree == right;
  72.     }
  73.   }
  74.