class MergeSorter  {

  @SuppressWarnings("unchecked")
  <T extends Comparable<T>> void 
  mergeSort(T array[]) {

    // Permute the given array so that 0 <= i <= j < array.length
    // implies a[i] <= a[j].

    final Comparable copy [] = new Comparable [array.length];

    if (mergeSort(array, 1, copy) != array)
      for (int i = 0; i < array.length; i++)
	array[i] = (T) copy[i];
    }


  private <T extends Comparable<T>> T []
  mergeSort(T source[], int size, T target[]) {

    // Assuming source is a sequence of sorted element segments of at
    // most the given size (that is, source[0..size - 1], source[size,
    // 2*size - 1], ..., source[i*size..min(source.length, (i +
    // 1)*size - 1], where i = floor(source.length/size)), store into
    // target a permutation of the elements in source so that 0 <= i
    // <= j < target.length implies target[i] <= target[j].

    final int n = source.length;

    if (size >= n)
      return source;

    for (int i = 0; i < n; i += size*2)
      merge(source, i, size, target);

    return mergeSort(target, size*2, source);
    }


  private <T extends Comparable<T>> void
  merge(T source[], int left, int size, T target[]) {

    // Assuming source is a sequence of sorted element segments of at
    // most the given size (that is, source[0..size - 1],
    // source[size..2*size - 1], ...,
    // source[i*size..min(source.length, (i + 1)*size - 1], where i =
    // floor(source.length/size)), store into target the merger of
    // adjacent segments from source (that is, target will be a
    // sequence of sorted element segments of at most twice the given
    // size).

    final int 
      n = source.length,
      mid = Math.min(left + size, n),
      right = Math.min(mid + size, n);
    int 
      m = mid,
      nextFree = left;

    while ((left < mid) && (m < right))
      if (source[left].compareTo(source[m]) > 0)
	target[nextFree++] = source[m++];
      else
	target[nextFree++] = source[left++];

    while (left < mid)
      target[nextFree++] = source[left++];
    while (m < right)
      target[nextFree++] = source[m++];

    assert nextFree == right;
    }
  }