1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
package com.jclark.xsl.util;
public class MergeSort {
private MergeSort() { }
public static void sort(Comparator cmp, Object[] src) {
sort(cmp, src, 0, src.length);
}
public static void sort(Comparator cmp, Object[] src, int off, int len) {
sort(cmp, src, off, len, new Object[len], 0);
}
public static void sort(Comparator cmp,
Object[] src, int off, int len,
Object[] temp, int tempOff) {
if (len <= 1)
return;
int halfLen = len/2;
sortCopy(cmp, src, off, halfLen, temp, tempOff);
sortCopy(cmp, src, off + halfLen, len - halfLen, temp, tempOff + halfLen);
merge(cmp, temp, tempOff, halfLen, len - halfLen, src, off);
}
private static void sortCopy(Comparator cmp,
Object[] src, int off, int len,
Object[] dest, int destOff) {
if (len <= 1) {
if (len != 0)
dest[destOff] = src[off];
return;
}
int halfLen = len/2;
sort(cmp, src, off, halfLen, dest, destOff);
sort(cmp, src, off + halfLen, len - halfLen, dest, destOff + halfLen);
merge(cmp, src, off, halfLen, len - halfLen, dest, destOff);
}
private static void merge(Comparator cmp,
Object[] src, int off1, int len1, int len2,
Object[] dest, int destOff) {
int off2 = off1 + len1;
if (len1 != 0 && len2 != 0) {
for (;;) {
if (cmp.compare(src[off1], src[off2]) <= 0) {
dest[destOff++] = src[off1++];
if (--len1 == 0)
break;
}
else {
dest[destOff++] = src[off2++];
if (--len2 == 0)
break;
}
}
}
for (; len1 > 0; --len1)
dest[destOff++] = src[off1++];
for (; len2 > 0; --len2)
dest[destOff++] = src[off2++];
}
}
|
