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;
}
}