Java合并排序递归的奇怪之处

Question

我正在对排序算法进行一些回顾，因为它们实际上在我的现实生活中并不经常出现，而这个让我发疯了。我也有一段时间没有接触 Java 了，所以我想也许我忘记了一些语言深奥的东西，但我不这么认为。

我发现成功或失败取决于我如何进行递归调用来拆分数组。因此，如果我使用 split 调用的返回值作为 merge 调用的参数，它就可以工作。但是，如果我先递归调用 split，然后调用 merge，则会失败。然而，在我看来，它们都应该起作用。这似乎与堆栈的展开方式有关，但我无法完全理解它。

static Comparable[] mergesort(Comparable[] src) {
    if (src.length < 2)
        return src;

    int middle = src.length / 2;
    if (src.length % 2 > 0)
        middle++;

    Comparable[] left = new Comparable[src.length / 2];
    Comparable[] right = new Comparable[middle];

    System.arraycopy(src, 0, left, 0, left.length);
    System.arraycopy(src, src.length / 2, right, 0, right.length);

    // THIS DOESN'T WORK, BUT I DON'T KNOW WHY
    // mergesort(left);
    // mergesort(right);
    // return mergearrays(left, right);
    // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    // 
    // THIS ONE DOES WORK
    // 
    return mergearrays(mergesort(left), mergesort(right));
}

static Comparable[] mergearrays(Comparable[] left, Comparable[] right) {

    Comparable[] retval = new Comparable[left.length + right.length];

    int i = 0, j = 0, k = 0;
    for (; i < left.length && j < right.length;) {
        if (left[i].compareTo(right[j]) >= 0) {
            retval[k++] = right[j++];
        } else
            retval[k++] = left[i++];

    }

    while (k < retval.length) {
        if (i < left.length) {
            retval[k++] = left[i++];
        }
        if (j < right.length) {
            retval[k++] = right[j++];
        }
    }

    return retval;
}

Answer 1

您的 mergearrays 方法创建一个新数组，在其中存储合并的排序数组。因此，如果您不使用 mergesort(left) 和 mergesort(right) 返回的数组(它们本身就是之前调用 mergearrays 创建的数组) code>)，您将丢弃已排序的数组并将未排序的数组(left 和 right)传递给 mergearrays。

因此这段代码是错误的:

mergesort(left); // returns a new sorted array which you ignore, doesn't modify left
mergesort(right); // returns a new sorted array which you ignore, doesn't modify right
return mergearrays(left, right); // merges two unsorted arrays, and therefore is wrong

虽然这段代码是正确的:

// merges the two sorted arrays returned by mergesort(left) and mergesort(right)
return mergearrays(mergesort(left), mergesort(right));

某些合并排序实现对原始数组执行合并步骤(即，它们对数组进行就地排序，而不是返回新的排序数组)，在这种情况下，mergearrays 方法和 >mergesort 需要返回任何内容，并且以下可以工作:

mergesort(left);
mergesort(right);
mergearrays(left, right);