Java实现归并排序输出异常，如何排查逻辑错误定位故障点？

核心问题 #

• 最致命的逻辑错误：merge函数仅把合并后的有序结果写入了temp数组，但全程没有更新原始数组arr。递归过程中所有层级的合并操作，都是基于最开始传入的未排序arr做元素比较，下层子区间的排序结果完全没有被上层使用，最终输出自然不符合预期。
• 同时存在两处语法错误：
  • Java中数组长度是属性而非方法，arr.length()需要改为arr.length
  • 主函数打印语句System.out.print(num+" ")末尾缺少分号

修复方案 #

最简单的修改方式是在merge函数的合并逻辑执行完成后，将temp中[l, r]区间的有序内容回写到arr的对应位置，保证上层递归合并时使用的是已经排好序的子区间数据。

修正后完整代码 #

static void main(String args[])
{
    int arr[] = {6,4,7,8,5,3,2,8,1};
    int temp[] = new int[arr.length];
    // 初始给temp赋值是非必要操作，可直接删除
    mergeSort(arr, temp, 0, arr.length-1);
    
    for(int num : temp)
    {
        System.out.print(num+" ");
    } 
}

//merge function comparing array and assigning to a new temp array.
static void merge(int arr[],int temp[], int l, int mid, int r)
{     
    int i = l;
    int j = mid+1;
    
    int index=l;
    while(i<=mid && j<=r)
    {   
        if(arr[i]<=arr[j])
        { 
            temp[index] = arr[i];
            i++;
        }
        else
        {
            temp[index] = arr[j];
            j++;
        }
        index++;
    }     
    while(i<=mid)
        {
            temp[index] = arr[i];
            i++;  
            index++;   
        }
        
    while(j<=r)
        {
            temp[index] = arr[j];
            j++;
            index++;
        }
    // 新增：将temp的有序区间回写到arr，供上层递归使用
    for (int k = l; k <= r; k++) {
        arr[k] = temp[k];
    }
}

//mergeSort function
static void mergeSort(int arr[],int temp[], int l, int r)
{
    if(l<r)
    {
        int mid = l + (r-l)/2;
        mergeSort(arr,temp,l,mid);
        mergeSort(arr,temp,mid+1,r);
        merge(arr,temp,l,mid,r);
    } 
}

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