Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement