java - 合并排序错误的问题

Question

我正在尝试实现合并排序，但遇到了合并功能:

这是我的功能:

public static void merge(Comparable[] a, Comparable[] aux, int low, int mid, int hi) {
    // Copy the elements to the aux array
    for(int i = low; i < a.length; i++) {
        aux[i] = a[i];
    }

    int i = low, j = mid + 1;
    for (int k = low; k <= hi; k++) {
        if      (i > mid)              a[k] = aux[j++];
        else if (j > hi)               a[k] = aux[i++];
        else if (less(aux[j], aux[i])) a[k] = aux[j++];
        else                           a[k] = aux[i++];
    }
}

运行以下输入:

[2, 4, 6, 8, 3, 5, 7, 9]

产生这个结果:

[2, 3, 3, 3, 3, 5, 7, 9]

这是调用本身:

    int mid = 0 + (my_array.length - 0) / 2;
    MergeSort.merge(my_array, my_array, 0, mid -1, my_array.length-1);

我不太确定。

Answer 1

a 和 aux 是同一个数组。因此，您首先将数组复制到其自身中，这是毫无用处的。然后，在第二个循环中，您在读取值时更改该值，这使一切都变得困惑。

不要传递两个(相同的)数组，而是在 merge 方法中创建一个新数组并返回它。