归并排序最有效的实现

Question

所以我想知道 Java 中合并排序最有效的实现是什么（如果它的时间效率会根据语言而变化）。这个问题可能很微不足道，但我的最终目标是向更有经验的程序员学习。这是我做的两个例子：

//version I made.
public static double[] mergeSort(double[] arreglo) {
    if (arreglo.length > 1) {
        int d = (arreglo.length / 2);
        double[] arreglo1 = Arrays.copyOfRange(arreglo, 0, d),
                arreglo2 = Arrays.copyOfRange(arreglo, d, arreglo.length);
        arreglo1 = mergeSort(arreglo1);
        arreglo2 = mergeSort(arreglo2);
        return merge(arreglo1, arreglo2);
    } else {
        return arreglo;
    }
}

public static double[] merge(double[] arreglo1, double[] arreglo2) {
    double[] convi = new double[arreglo1.length + arreglo2.length];
    for (int i = 0, m1 = 0, m2 = 0; i < convi.length; i++) {
        if (arreglo1.length > m1 && arreglo2.length > m2) {
            if (arreglo1[m1] <= arreglo2[m2])
                convi[i] = arreglo1[m1++];
            else {
                convi[i] = arreglo2[m2++];
            }
        } else {
            convi[i] = (arreglo1.length == m1) ? arreglo2[m2++] : arreglo1[m1++];
        }
    }
    return convi;
}

//Taken out of Cormens book.
public static void mergeSort(int[] arreglo, int i, int f) {
    if (f > i) {
        int d = ((i + f) / 2);
        mergeSort(arreglo, i, d);
        mergeSort(arreglo, d + 1, f);
        merge(arreglo, i, d, f);
    }
}


public static void merge(int[] arreglo, int i, int m, int f) {
    int n1 = (m - i) + 1;
    int n2 = (f - m);
    int[] mitad1 = new int[n1 + 1];
    int[] mitad2 = new int[n2 + 1];
    for (int v = 0; v < n1; v++) {
        mitad1[v] = arreglo[i + v];
    }
    for (int p = 0; p < n2; p++) {
        mitad2[p] = arreglo[p + m + 1];
    }
    mitad1[n1] = Integer.MAX_VALUE;
    mitad2[n2] = Integer.MAX_VALUE;
    for (int r = i, m1 = 0, m2 = 0; r <= f; r++) {
        if (mitad1[m1] <= mitad2[m2]) {
            arreglo[r] = mitad1[m1];
            m1++;
        } else {
            arreglo[r] = mitad2[m2];
            m2++;
        }
    }
}

Answer 1

以下程序是从Robert Sedgewick\'s Algorithms in C++, Parts 1-4中给出的 C++ 示例翻译而来的

\n\n

它引入了一种类型的改进。它将整个排序数组复制到一个辅助数组中以供进一步处理。接下来，通过在辅助数组和原始数组之间交替来对辅助数组进行递归分割，这样就不会发生合并数组的额外复制操作。基本上，该算法在每次递归调用中切换输入数组和辅助数组的角色。例如，从概念上来说：

\n\n

常规归并排序：

\n\n

- 合并

\n\n

(((8) (5))((2) (3)))(((1) (7))((4) (6)))\n\n(( 5 8 )( 2 3 ))(( 1 7 )( 4 6 ))\n\n-- copy back and ignore previous (UNNECESSARY)\n\n(( 5 8 )( 2 3 ))(( 1 7 )( 4 6 ))\n

\n\n

\xe2\x80\x93 \xe2\x80\x93 \xe2\x80\x93 \xe2\x80\x93 \xe2\x80\x93 \xe2\x80\x93 \xe2\x80\x93 \xe2\x80\x93

\n\n

这个程序：

\n\n

- 合并

\n\n

(((8) (5))((2) (3)))(((1) (7))((4) (6)))\n\n(( 5 8 )( 2 3 ))(( 1 7 )( 4 6 ))\n

\n\n

--向后合并

\n\n

( 2 3 5 8 )( 1 4 6 7 )\n\n(( 5 8 )( 2 3 ))(( 1 7 )( 4 6 ))    \n

\n\n

此外，将数组分成两半后给出足够小的数组，该算法使用该算法，insertion sort因为它在小数据集上的性能比merge sort. 确切何时使用的阈值insertion sort可以通过反复试验来确定。

\n\n

代码：

\n\n

static int M = 10;\n\n//insertion sort to be used once the mergesort partitions become small enough\nstatic void insertionsort(int[] a, int l, int r) {\n    int i, j, temp;\n    for (i = 1; i < r + 1; i++) {\n        temp = a[i];\n        j = i;\n        while ((j > 0) && a[j - 1] > temp) \n        {\n            a[j] = a[j - 1];\n            j = j - 1;\n        }\n        a[j] = temp;\n    }\n}\n\n//standard merging two sorted half arrays into single sorted array\nstatic void merge(int[] merged_a, int start_a, int[] half_a1, int start_a1, int size_a1, \n                         int[] half_a2, int start_a2, int size_a2) {\n    int i, j, k;\n    int total_s = size_a1 + size_a2;\n    for (i = start_a1, j = start_a2, k = start_a; k < (total_s); k++) {\n        // if reached end of first half array, run through the loop \n        // filling in only from the second half array\n        if (i == size_a1) {\n            merged_a[k] = half_a2[j++];\n            continue;\n        }\n        // if reached end of second half array, run through the loop \n        // filling in only from the first half array\n        if (j == size_a2) {\n            merged_a[k] = half_a1[i++];\n            continue;\n        }\n        // merged array is filled with the smaller element of the two \n        // arrays, in order\n        merged_a[k] = half_a1[i] < half_a2[j] ?\n                      half_a1[i++] : half_a2[j++];\n    }\n}\n\n//merge sort data during merging without the additional copying back to array\n//all data movement is done during the course of the merges\nstatic void mergesortNoCopy(int[] a, int[] b, int l, int r) {\n    if (r - l <= M) {\n        insertionsort(a + l, l, r - l);\n        return;\n    }\n    int m = (l + r) / 2;\n    //switch arrays to msort b thus recursively writing results to b\n    mergesortNoCopy(b, a, l, m); //merge sort left\n    mergesortNoCopy(b, a, m + 1, r); //merge sort right\n    //merge partitions of b into a\n    merge(a, l, b, l, m - l + 1, b, m + 1, r - m); //merge\n}\n\nstatic void mergesort(int[] a) {\n    int[] aux = Arrays.copyOf(a, a.length);\n    mergesortNoCopy(a, aux, 0, a.length - 1);\n}\n

\n\n

其他一些可能的改进：

\n\n

如果已经排序则停止。

\n\n

检查前半部分 \xe2\x89\xa4 中最大的项目是否是后半部分中最小的项目。\n有助于部分排序的数组。

\n\n

// after split, before merge\nif (a[mid] <= a[mid + 1]) return;\n

\n\n

编辑：这是我在不同版本的合并排序及其改进中找到的一份很好的文档。

\n