public class MergeSorter
1: import java.util.*;
3: /**
4: This class carries out the merge sort algorithm.
5: */
6: public class MergeSorter
7: {
8: /**
9: Sorts an array, using the merge sort algorithm.
10: @param a the array to sort
11: @param comp the comparator to compare array elements
12: */
13: public static <E> void sort(E[] a, Comparator<? super E> comp)
14: {
15: mergeSort(a, 0, a.length - 1, comp);
16: }
18: /**
19: Sorts a range of an array, using the merge sort
20: algorithm.
21: @param a the array to sort
22: @param from the first index of the range to sort
23: @param to the last index of the range to sort
24: @param comp the comparator to compare array elements
25: */
26: private static <E> void mergeSort(E[] a, int from, int to,
27: Comparator<? super E> comp)
28: {
29: if (from == to) return;
30: int mid = (from + to) / 2;
31: // Sort the first and the second half
32: mergeSort(a, from, mid, comp);
33: mergeSort(a, mid + 1, to, comp);
34: merge(a, from, mid, to, comp);
35: }
37: /**
38: Merges two adjacent subranges of an array
39: @param a the array with entries to be merged
40: @param from the index of the first element of the
41: first range
42: @param mid the index of the last element of the
43: first range
44: @param to the index of the last element of the
45: second range
46: @param comp the comparator to compare array elements
47: */
48: private static <E> void merge(E[] a,
49: int from, int mid, int to, Comparator<? super E> comp)
50: {
51: int n = to - from + 1;
52: // Size of the range to be merged
54: // Merge both halves into a temporary array b
55: Object[] b = new Object[n];
57: int i1 = from;
58: // Next element to consider in the first range
59: int i2 = mid + 1;
60: // Next element to consider in the second range
61: int j = 0;
62: // Next open position in b
64: // As long as neither i1 nor i2 past the end, move
65: // the smaller element into b
66: while (i1 <= mid && i2 <= to)
67: {
68: if (comp.compare(a[i1], a[i2]) < 0)
69: {
70: b[j] = a[i1];
71: i1++;
72: }
73: else
74: {
75: b[j] = a[i2];
76: i2++;
77: }
78: j++;
79: }
81: // Note that only one of the two while loops
82: // below is executed
84: // Copy any remaining entries of the first half
85: while (i1 <= mid)
86: {
87: b[j] = a[i1];
88: i1++;
89: j++;
90: }
92: // Copy any remaining entries of the second half
93: while (i2 <= to)
94: {
95: b[j] = a[i2];
96: i2++;
97: j++;
98: }
100: // Copy back from the temporary array
101: for (j = 0; j < n; j++)
102: a[from + j] = (E) b[j];
103: }
104: }