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

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 包括在内。 j 是 B 的索引，它从 mid+1 到 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”的意思是“追加到合并数组并增加适当的数组计数器”。

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

How to understand abstract in-place merge sort

sorting

merge

in-place