自底向上归并排序的实现中是否存在可能的勘误表

Question

以下代码片段来自 Robert SedgeWick 和 Kevin Wayne 合着的《算法》一书。

public class MergeBU {

    // This class should not be instantiated.
    private MergeBU() { }

    // stably merge a[lo..mid] with a[mid+1..hi] using aux[lo..hi]
    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {

        // copy to aux[]
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k]; 
        }

        // merge back to a[]
        int i = lo, j = mid+1;
        for (int k = lo; k <= hi; k++) {
            if      (i > mid)              a[k] = aux[j++];  // this copying is unneccessary
            else if (j > hi)               a[k] = aux[i++];
            else if (less(aux[j], aux[i])) a[k] = aux[j++];
            else                           a[k] = aux[i++];
        }

    }

    /**
     * Rearranges the array in ascending order, using the natural order.
     * @param a the array to be sorted
     */
    public static void sort(Comparable[] a) {
        int n = a.length;
        Comparable[] aux = new Comparable[n];
        for (int len = 1; len < n; len *= 2) {
            for (int lo = 0; lo < n-len; lo += len+len) {
                int mid  = lo+len-1;
                int hi = Math.min(lo+len+len-1, n-1);
                merge(a, aux, lo, mid, hi);
            }
        }
        assert isSorted(a);
    }
//other methods
}

我的问题是关于排序方法的内部 for 循环条件。

如果输入数组有 10 个元素，对长度为 4 的子数组进行合并的数组传递将保留最后两个元素，它们相对于彼此排序但不相对于其他元素。

在下一轮中，用于合并的子数组的长度变为 8，并且相对于其他元素，最后两个元素仍未合并。这是长度为 10 的数组的最后一次传递。

因此，由于 lo < n-len 检查，最后两个元素相对于数组中的其他元素保持未排序状态。本节在任何时候都没有说数组中的元素数应该是 2 的幂。这是勘误表还是我遗漏了什么？

我一定是忽略了一些东西，因为下面的测试代码正确地排序了我的 10 元素数组。

public static void main(String[] args) {
        Integer[] array = {1,2,3,4,5,6,7,8,-50, -80};
        MergeBU.sort(array);
        System.out.println(Arrays.toString(array));
    }

谁能帮我解决一下。

Answer 1

您的分析不正确。合并过程如下。

在len = 4 的传递上，它将合并两个子数组[0-3] 和[4-7]。最后两项没有合并是正确的。

当len = 8时，合并两个子数组[0-7]和[8-9].

当循环控制变量递增时，我怀疑你误会了。您应该在调试器中单步执行 sort 方法，注意两个循环中 lo 和 len 的值。

顺便说一下，归并排序的定义中没有任何内容要求长度是 2 的幂。但是，处理不是 2 的幂的数组会增加一些复杂性。这就是 merge 循环中的 if (i > mid) 和 if (j > hi) 条件句的原因。

自底向上归并排序的实现中是否存在可能的勘误表

Is there a possible errata in this implementation of bottom up merge sort

java

sorting

algorithm

mergesort