递归归并排序未实现数组排序问题求助

你的归并排序代码存在两个关键问题，导致输出未排序的原数组：

1. 未接收mergeSort返回的排序后数组 #

你的mergeSort方法是创建并返回新的排序数组，不会修改传入的原数组。但在main方法中，你调用mergeSort(a)后没有将返回值赋值给任何变量，直接打印原数组a，自然输出的是未排序的初始状态。

修复方法：将mergeSort的返回值赋值给a，再打印：

public static void main(String[] args) {
    int[] a = {2, 1, 3, 4, 9, 6, 7};
    a = mergeSort(a); // 接收排序后的新数组
    System.out.println(Arrays.toString(a));
}

2. merge方法未处理元素相等的情况 #

在merge方法的while循环中，你只判断了a[indexa] < b[indexb]和a[indexa] > b[indexb]的情况，遗漏了两者相等的场景。此时两个指针都不会递增，循环会陷入死循环（如果数组中有相等元素的话）。

修复方法：将第二个条件改为else，覆盖大于等于的情况（包括相等）：

public static int[] merge(int[] a, int[] b) {
    int indexa = 0; 
    int indexb = 0; 
    int i =0;
    int[] c = new int[a.length + b.length];
    
    while (indexa < a.length && indexb < b.length) {
        if (a[indexa] < b[indexb]) {
            c[i++] = a[indexa++];
        } else { // 覆盖大于等于的情况，包括相等
            c[i++] = b[indexb++];
        }
    }

    while (indexa < a.length) {
        c[i++] = a[indexa++];
    }
    while (indexb < b.length) {
        c[i++] = b[indexb++];
    }
    return c;
}

修复后的运行效果 #

修改后运行main方法，会输出正确的排序结果：[1, 2, 3, 4, 6, 7, 9]

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