运行 我的合并排序函数 (Java) 时出现 StackOverflowError

Question

我正在尝试实现合并排序功能，但在尝试 运行 时收到 WhosebugError 异常。我看到了另一个与我的类似的问题，答案是关于改变中点的计算方式。我试图更改中点，但仍然遇到相同的 Whosebug 错误。

感谢观看。

public static void mergeSort(int [] arr, int low, int high) {

        if (low < high) {
            int mid = (low + high)/2;

            mergeSort(arr, low, mid + 1);
            mergeSort(arr, mid, high);          
            merge(arr, low, mid, high);
        }
    }

    public static void merge(int [] arr, int low, int mid, int high) {

        int n1 = mid - low + 1;
        int n2 = high - mid;

        int [] leftArr = new int[n1];
        int [] rightArr = new int[n2];

        for (int i = 0; i < n1; i++) leftArr[i] = arr[low + i];
        for (int j = 0; j < n2; j++) rightArr[j] = arr[mid + j + 1];

        int i = 0;
        int j = 0;

        int k = 1;

        while (i < n1 && j < n2) {
            if (leftArr[i] < rightArr[j]) {
                arr[k] = leftArr[i++];
            }
            else {
                arr[k] = rightArr[j++];
            }
            k++;
        }
        while (i < n1) arr[k++] = leftArr[i++];
        while (j < n2) arr[k++] = rightArr[j++];
    }

Answer 1

您实现了合并排序功能 wrong.it 应该如下所示

if (low < high) {
        int mid = (low + high)/2;

        mergeSort(arr, low, mid -1);
        mergeSort(arr, mid, high);          
        merge(arr, low, mid, high);
    }

并且在你已经初始化的合并函数中

k=1;

但应该是

k=low;

因为如果你每次都初始化 k=1 那么它将覆盖数组元素。