如何理解抽象的就地归并排序

Question

我无法理解合并排序。例如，为什么 var I 可以比 var mid 大？这是不可能的，因为 3 个变量：lo 表示低，hi 表示高，mid 表示平均值？

所以我看不到如果 i>mid 会发生什么。

public static void merge(Comparable[] a, int lo, int mid, int hi) {

int i = lo, j = mid + 1;
for (int k = 0; k <= hi; k++) {
    aux[k] = a[k];
}
for (int k = lo; 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++];
    }
    }
}

Answer 1

就地归并排序是这样工作的：如果你的数组是空的或者有一个元素，它就会被排序。如果它有两个元素，您可以通过适当交换来轻松对其进行排序。如果它有两个以上的元素，请执行以下操作：

• 在中点将数组分成两半mid；
• 在左半部分调用合并排序；
• 在右侧调用合并排序；
• 通过从两个子数组中挑选最小的头元素来合并数组，直到它们用完为止。

您发布的代码不是完整的合并排序；这只是合并部分。此时，您有两个已排序的子数组。需要复制两个子数组，以便您可以用排序的值填充原始数组。

在此实现中，子数组存储在一个连续数组中aux：

   lo         A         mid     B       hi
    +---+---+---+---+---++---+---+---+---+
    | 1 | 5 | 6 | 8 | 9 || 2 | 3 | 4 | 7 |
    +---+---+---+---+---++---+---+---+---+
    i ->                 j ->

这里，i是索引到A，它从 0 运行到mid - 1。j是 into 的索引B，它从mid到hi包含在内。k循环的控制索引是合并操作的计数；每次迭代都有一个。

所有整数值都是数组索引；它们不代表平均值等值。合并算法依赖于被排序的子数组。

要注释您的合并循环：

for (int k = lo; k <= hi; k++) {
    if (i > mid) {                      // A is exhausted, ...
        a[k] = aux[j++];                // ..., take B[j]
    } else if (j > hi) {                // B is exhausted, ...
        a[k] = aux[i++];                // ..., take A[i]
    } else if(less(aux[j], aux[i])) {   // B[j] < A[i], ...
        a[k] = aux[j++];                // ..., take B[j]
    } else {                            // A[i] <= B[j], ...
        a[k] = aux[i++];                // ..., take A[i]
    }
}

这里，“take”的意思是“追加到合并数组并推进适当的数组计数器”。