• API
• FAQ
• Tools
• Trends
• Archive
SHARE
TWEET

# r clayton

a guest Nov 19th, 2009 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. class MergeSorter  {
2.
3.   @SuppressWarnings("unchecked")
4.   <T extends Comparable<T>> void
5.   mergeSort(T array[]) {
6.
7.     // Permute the given array so that 0 <= i <= j < array.length
8.     // implies a[i] <= a[j].
9.
10.     final Comparable copy [] = new Comparable [array.length];
11.
12.     if (mergeSort(array, 1, copy) != array)
13.       for (int i = 0; i < array.length; i++)
14.         array[i] = (T) copy[i];
15.     }
16.
17.
18.   private <T extends Comparable<T>> T []
19.   mergeSort(T source[], int size, T target[]) {
20.
21.     // Assuming source is a sequence of sorted element segments of at
22.     // most the given size (that is, source[0..size - 1], source[size,
23.     // 2*size - 1], ..., source[i*size..min(source.length, (i +
24.     // 1)*size - 1], where i = floor(source.length/size)), store into
25.     // target a permutation of the elements in source so that 0 <= i
26.     // <= j < target.length implies target[i] <= target[j].
27.
28.     final int n = source.length;
29.
30.     if (size >= n)
31.       return source;
32.
33.     for (int i = 0; i < n; i += size*2)
34.       merge(source, i, size, target);
35.
36.     return mergeSort(target, size*2, source);
37.     }
38.
39.
40.   private <T extends Comparable<T>> void
41.   merge(T source[], int left, int size, T target[]) {
42.
43.     // Assuming source is a sequence of sorted element segments of at
44.     // most the given size (that is, source[0..size - 1],
45.     // source[size..2*size - 1], ...,
46.     // source[i*size..min(source.length, (i + 1)*size - 1], where i =
47.     // floor(source.length/size)), store into target the merger of
48.     // adjacent segments from source (that is, target will be a
49.     // sequence of sorted element segments of at most twice the given
50.     // size).
51.
52.     final int
53.       n = source.length,
54.       mid = Math.min(left + size, n),
55.       right = Math.min(mid + size, n);
56.     int
57.       m = mid,
58.       nextFree = left;
59.
60.     while ((left < mid) && (m < right))
61.       if (source[left].compareTo(source[m]) > 0)
62.         target[nextFree++] = source[m++];
63.       else
64.         target[nextFree++] = source[left++];
65.
66.     while (left < mid)
67.       target[nextFree++] = source[left++];
68.     while (m < right)
69.       target[nextFree++] = source[m++];
70.
71.     assert nextFree == right;
72.     }
73.   }
RAW Paste Data
Top