MergeSort归并排序代码排错求助：输入数组排序后无变化问题

嘿，我太懂你现在的挫败感了——花了功夫写的归并排序，结果输出和原数组一模一样，试了各种办法都没搞定，确实让人挠头。咱们来拆解下你的代码，很快就能揪出问题根源！

核心问题：基准情况的返回值完全错误 #

你的mergeSort方法里，基准条件的返回值犯了一个致命的类型错误，这是排序完全失效的根本原因：

if (arr.length == 1) {
    return arr[0];
}

这里arr[0]是单个int数值，但方法声明的返回类型是int[]（整数数组）。这种类型不匹配的错误直接破坏了递归的逻辑链条：当递归拆分到单元素数组时，你没有返回正确的子数组，后续的merge操作根本拿不到已排序的子数组，整个排序流程相当于“走了个过场”，最终直接返回了原数组。

修复方案 #

把基准情况的返回值改成包含该单元素的数组即可：

public static int[] mergeSort(int[] arr) {
    if (arr.length == 1) {
        // 返回包含当前元素的单元素数组，保证类型匹配与递归逻辑正确
        return new int[]{arr[0]};
    }
    int[] arr1 = new int[arr.length / 2];
    int[] arr2 = new int[arr.length - arr1.length];
    for (int i = 0; i < arr1.length; i++) {
        arr1[i] = arr[i];
    }
    for (int i = 0; i < arr2.length; i++) {
        arr2[i] = arr[i + arr1.length];
    }
    arr1 = mergeSort(arr1);
    arr2 = mergeSort(arr2);
    return merge(arr1, arr2);
}

额外优化建议（可选） #

你的merge方法逻辑是正确的，但后面的两个while循环可以简化——不需要额外判断哪个数组还有剩余元素，因为前面的循环已经保证其中一个数组被完全遍历：

private static int[] merge(int[] a, int[] b) {
    int[] c = new int[a.length + b.length];
    int counterA = 0;
    int counterB = 0;
    int counterC = 0;
    while (counterA != a.length && counterB != b.length) {
        if (a[counterA] < b[counterB]) {
            c[counterC++] = a[counterA++];
        } else {
            c[counterC++] = b[counterB++];
        }
    }
    // 处理a数组剩余元素
    while (counterA < a.length) {
        c[counterC++] = a[counterA++];
    }
    // 处理b数组剩余元素
    while (counterB < b.length) {
        c[counterC++] = b[counterB++];
    }
    return c;
}

测试验证 #

修复后，用你提供的测试输入9, 1, 7, 5, 7, 2, 2, 9, 8, 9，就能得到预期的排序结果：1, 2, 2, 5, 7, 7, 8, 9, 9, 9。

以后再遇到递归算法问题，建议在递归的关键步骤（比如拆分后、merge前）打印子数组内容，这样能快速定位递归流程是否符合预期~

内容的提问来源于stack exchange，提问作者Ben Tseng