@SuppressWarnings("unchecked")
static <T extends Comparable<T>> void
merge(Comparable source[], int left, int mid, int right, T target[]) {
// Merge the sorted array segment source[left..mid - 1] with the sorted
// array segment source[mid..right - 1] to form the sorted array segment
// target[left..right - 1].
int m = mid;
int nextFree = left;
while ((left < mid) && (m < right))
if (source[left].compareTo(source[m]) > 0)
target[nextFree++] = (T) source[m++];
else
target[nextFree++] = (T) source[left++];
while (left < mid)
target[nextFree++] = (T) source[left++];
while (m < right)
target[nextFree++] = (T) source[m++];
assert nextFree == right;
}