了解合并排序的工作原理

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);
}

代码有效,但我很难理解它.

1. 我理解的目的

   if (hi <= lo) {
       return;
   }
   

   但我不知道返回执行后会发生什么.

2. 我不明白为什么合并函数中的最后一个存在.如果算法被分裂,直到aux是[3,5],我想升序排序时,else if将比较5 < 3,这将跳转到其他人,并应更换2倍的值.

编辑:我使用调试器进行了一些操作,对于此示例(3 33 1 55 66 34 67 45 23),它使用前2个值到达合并功能.最后一个如果比较33 <3并输入最后一个.如果这些值的顺序正确,这行代码的重点是什么？在数组[k] = aux [i ++]之后; 执行array [0]的值是相同的,因为aux [i ++]是数组[1]是奇数

Answer 1

1. 在该sort方法中，问题被划分为更小的子问题。当要排序的范围仅为一或零宽时，无需执行任何操作，并且可以关闭该方法。这是因为只有一个元素是根据定义排序的。这是m0skit0所说的递归的停止条件。

2. 该算法中不交换元素。该方法尝试合并两个已排序的数组。有两个索引i和j。当i到达中间时，右侧部分的所有元素都将添加到结果数组中。如果j到达右边界，则将左侧部分的所有元素添加到结果中。这是前两种情况。
   现在，在最后两种情况下，算法尝试找出由i和索引的当前元素中的哪一个j是最小值，并将其添加到结果数组中。在第三种情况下，at 的元素j较小并添加到结果数组中。i在第四种情况下，选择了元素 at 。