以下程序是从 C++ 示例翻译而来的Robert Sedgewick 的 C++ 算法,第 1-4 部分
它引入了一种类型的改进。它将整个排序数组复制到一个辅助数组中以供进一步处理。接下来,通过在辅助数组和原始数组之间交替来对辅助数组进行递归分割,这样就不会发生合并数组的额外复制操作。基本上,该算法在每次递归调用中切换输入数组和辅助数组的角色。例如,从概念上来说:
常规归并排序:
--merge
(((8) (5))((2) (3)))(((1) (7))((4) (6)))
(( 5 8 )( 2 3 ))(( 1 7 )( 4 6 ))
-- copy back and ignore previous (UNNECESSARY)
(( 5 8 )( 2 3 ))(( 1 7 )( 4 6 ))
– – – – – – – –
这个程序:
--merge
(((8) (5))((2) (3)))(((1) (7))((4) (6)))
(( 5 8 )( 2 3 ))(( 1 7 )( 4 6 ))
--向后合并
( 2 3 5 8 )( 1 4 6 7 )
(( 5 8 )( 2 3 ))(( 1 7 )( 4 6 ))
此外,将数组分成两半后给出足够小的数组,该算法使用insertion sort
因为它在小数据集上的表现比merge sort
。确切何时使用的阈值insertion sort
可以通过反复试验来确定。
代码:
static int M = 10;
//insertion sort to be used once the mergesort partitions become small enough
static void insertionsort(int[] a, int l, int r) {
int i, j, temp;
for (i = 1; i < r + 1; i++) {
temp = a[i];
j = i;
while ((j > 0) && a[j - 1] > temp)
{
a[j] = a[j - 1];
j = j - 1;
}
a[j] = temp;
}
}
//standard merging two sorted half arrays into single sorted array
static void merge(int[] merged_a, int start_a, int[] half_a1, int start_a1, int size_a1,
int[] half_a2, int start_a2, int size_a2) {
int i, j, k;
int total_s = size_a1 + size_a2;
for (i = start_a1, j = start_a2, k = start_a; k < (total_s); k++) {
// if reached end of first half array, run through the loop
// filling in only from the second half array
if (i == size_a1) {
merged_a[k] = half_a2[j++];
continue;
}
// if reached end of second half array, run through the loop
// filling in only from the first half array
if (j == size_a2) {
merged_a[k] = half_a1[i++];
continue;
}
// merged array is filled with the smaller element of the two
// arrays, in order
merged_a[k] = half_a1[i] < half_a2[j] ?
half_a1[i++] : half_a2[j++];
}
}
//merge sort data during merging without the additional copying back to array
//all data movement is done during the course of the merges
static void mergesortNoCopy(int[] a, int[] b, int l, int r) {
if (r - l <= M) {
insertionsort(a + l, l, r - l);
return;
}
int m = (l + r) / 2;
//switch arrays to msort b thus recursively writing results to b
mergesortNoCopy(b, a, l, m); //merge sort left
mergesortNoCopy(b, a, m + 1, r); //merge sort right
//merge partitions of b into a
merge(a, l, b, l, m - l + 1, b, m + 1, r - m); //merge
}
static void mergesort(int[] a) {
int[] aux = Arrays.copyOf(a, a.length);
mergesortNoCopy(a, aux, 0, a.length - 1);
}
其他一些可能的改进:
如果已经排序则停止。
检查前半部分最大的项是否≤后半部分的最小项。
对部分有序数组有帮助。
// after split, before merge
if (a[mid] <= a[mid + 1]) return;
EDIT:这里有一个好文件我发现了不同版本的合并排序及其改进。