Java归并排序程序无法正确排序数组的故障排查

问题现象 #

传入测试数组{2,7,9,5,3}调用归并排序逻辑，最终输出结果为0,0,0,3,5，未得到预期的升序排序结果。

错误根因 #

代码中merge合并函数存在两处核心逻辑错误：

• 临时数组回写原数组的范围错误：每次合并仅处理原数组[low, high]闭区间内的元素，但当前回写循环从下标0开始遍历临时数组，会将临时数组未赋值位置的默认int值0覆盖到原数组的非当前处理区间。递归到合并右半段（下标3、4，对应元素5、3）时，临时数组前3位都是默认0，回写时直接把原数组前3位已经排好序的2、7、9全部冲为0，正好对应出现的异常输出。
• 临时数组定义硬编码：固定创建长度为5的临时数组，代码无法适配其他长度的输入数组，换输入时会直接触发数组下标越界异常；同时索引起始值和当前合并段的起始下标绑定，导致临时数组前置位置空占内存，还容易引入默认值脏数据。

修复方案 #

1. 去掉临时数组的硬编码长度，按当前待合并的区间长度创建对应大小的临时数组，避免内存浪费和越界问题
2. 临时数组的写入索引从0开始，专门存储当前待合并段的排序结果，不要用原数组的下标作为临时数组的写入起始位置
3. 回写时仅遍历当前合并段的范围，将临时数组的内容按偏移量写回原数组的[low, high]区间，不要覆盖其他位置的已有排序结果

修正后可运行代码 #

public class merge_sort {
    public static void merge(int arr[],int low,int mid,int high){
        int i=low;
        int j=mid+1;
        int k=0; // 临时数组从0下标开始存储元素
        // 按当前合并区间长度创建临时数组，不再硬编码固定长度
        int brr[]=new int[high - low + 1];
        while(i<=mid&&j<=high){
            if(arr[i]<arr[j]){
                brr[k]=arr[i];
                i++;
                k++;
            }
            else{
                brr[k]=arr[j];
                k++;
                j++;
            }
        }
        while(i<=mid){
            brr[k]=arr[i];
            i++;
            k++;
        }
        while(j<=high){
            brr[k]=arr[j];
            j++;
            k++;
        }
        // 仅回写当前处理的[low, high]区间，不覆盖其他位置的有效数据
        for (int z = 0; z < brr.length; z++)
        {
            arr[low + z]=brr[z];
        }
    }

    public static void mergesort(int arr[], int low, int high) {
        if(low<high){
            int mid=(low+high)/2;
            mergesort(arr,low,mid);
            mergesort(arr,mid+1,high);
            merge(arr,low,mid,high);
        }
    }

    public static void main(String args[]) {
        int arr[]={2,7,9,5,3};
        int arr_size=5;
        mergesort(arr,0,arr_size-1);
        for (int i = 0; i < arr_size; i++)
        {
            System.out.println(arr[i]);
        }
    }
}

运行修正后的代码，输入测试数组可以得到正确的升序输出2,3,5,7,9。

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