class MergeSorter
extends Sorter {
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))
// permutation(source[left'..left-1] ++ source[mid..m-1]) ==
// target[left..nextFree]
// sorted(target[left..lextFree])
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;
}
@SuppressWarnings("unchecked")
public <T extends Comparable<T>> void
sort(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];
}
}