了解合并排序的工作原理

Question

private void merge(int[] array, int[] aux, int low, int mid, int hi) {
    int i = low, j = mid + 1, k;

    for (k = low; k <= hi; k++) {
        aux[k] = array[k];
    }
    for (k = low; k <= hi; k++) {
        if (i > mid) {
            array[k] = aux[j++];
        } else if (j > hi) {
            array[k] = aux[i++];
        } else if (aux[j] <  aux[i]) {
            array[k] = aux[j++];
        } else /* if (aux[i] <= aux[j] */ {
            array[k] = aux[i++];
        }
    }
}

private void sort(int[] array, int[] aux, int lo, int hi) {   
    if (hi <= lo) {
        return;
    }

    int mid = lo + (hi - lo) / 2;
    sort(array, aux, lo, mid);
    sort(array, aux, mid + 1, hi);
    merge(array, aux, lo, mid, hi);
}

public void mergeSort() {      
    int aux[] = new int[n];
    sort(ar, aux, 0, n - 1);
}

该代码有效，但我无法理解它。

我明白
的目的
```
if (hi <= lo) {
    return;
}
```
但我不知道执行return时会发生什么。
我不明白为什么合并函数中的最后一个else存在。如果算法分裂直到 aux 是 [3,5] 并且我想升序排序，else if 将比较 5 < 3 将跳转到 else 并且它应该交换 2值。

编辑：我用调试器玩了一下，对于这个例子 (3 33 1 55 66 34 67 45 23) 它到达了具有前 2 个值的合并函数。最后一个 else if 比较 33 < 3 并进入最后一个 else 。如果这些值的顺序正确，这行代码的意义何在？在 array[k] = aux[i++]; 之后array[0] 的值是奇数，因为 aux[i++] 是 array[1]

Answer 1

在 sort 方法中，问题被分成更小的子问题。当要排序的范围只有一或零宽时，无事可做，可以关闭该方法。那是因为只有一个元素是按定义排序的。是递归的停止条件.
在此算法中不交换元素。该方法尝试合并两个排序数组。有两个索引 i 和 j。当i到达中间时，右边部分的所有元素都被添加到结果数组中。如果 j 到达右边界，则将左侧部分的所有元素添加到结果中。以上就是前两种情况。
现在，在最后两种情况下，算法会尝试找出由 i 和 j 索引的当前元素中的最小值，并将其添加到结果数组中。在第三种情况下，j 处的元素较小并添加到结果数组中。在第四种情况下，选择了 i 处的元素。

了解合并排序的工作原理

Understanding how merge sort works

java

sorting

mergesort