遵循 Jenny 的伪代码的 Java 归并排序

Question

我正在执行合并排序，遵循https://www.youtube.com/watch?v=jlHkDBEumP0上的伪代码 GFG 和 Programiz 提供的代码略有不同，但我想以这种方式实现，因为这就是我的理解。 但我没有得到正确的结果。问题似乎与复制原始数组有关。我做错了什么？

归并排序

    public static void mergeSort(int[] arr, int low, int up) {  // lower bound & upper bound
        if (low < up) {
            int mid = (low + up) / 2;     // get middle
            mergeSort(arr, low, mid);     // continue to divide lower half
            mergeSort(arr, low + 1, up);  // continue to divide upper half
            merge(arr, low, mid, up);     // sort and merge halves
        }
    }

合并

    public static void merge(int[] arr, int low, int mid, int up) {
        int i = low;      // i starts at lower bound
        int j = mid + 1;  // j starts at start of second half
        int k = low;
        
        int[] tempArr = new int [arr.length];  // create temp array

        while (i <= mid && j <= up) {
            if (arr[i] <= arr[j]) {
                tempArr[k] = arr[i];
                i++;
            }
            else {
                tempArr[k] = arr[j];
                j++;
            }
            k++;
        }
        
        // if (i > mid) {
            while (j <= up) {  // i is done, but j may not.
                tempArr[k] = arr[j];
                j++;
                k++;
            }
        // }
        // else {
            while (i <= mid) {  // j is done, but i may not.
                tempArr[k] = arr[i];
                i++;
                k++;
            }
        // }

        for (k = low; k <= up; k++) {  // copy & paste to original array
            arr[k] = tempArr[k];
        }
    }

主要方法

    public static void main(String[] args) {
        int[] myArr = new int[] {4, 7, 1, -4, 8, 3, 0 ,20, 1, 12};
        mergeSort(myArr, 0, myArr.length - 1);
        for (int i : myArr) {
            System.out.print(i + " ");
        }
    }

Answer 1

应该是这样的：

    public static void mergeSort(int[] arr, int low, int up) {  // lower bound & upper bound
        if (low < up) {
            int mid = (low + up) / 2;     // get middle
            mergeSort(arr, low, mid);     // continue to divide lower half
            mergeSort(arr, mid + 1, up);  // continue to divide upper half
            merge(arr, low, mid, up);     // sort and merge halves
        }
    }

你做了

low + 1

，而不是

mid + 1

。