MergeSort方法无法修改传入数组问题求助

你的代码核心问题出在MergeSort类的merge方法逻辑错误，和类是否单独存放无关——之前单独存放时可能测试用例未触发这个bug，合并后才暴露。

具体错误点 #

在merge方法中，你将处理剩余元素的两个while循环写在了外层的while (i < n1 && j < n2)循环内部，导致外层循环仅执行一次就直接进入剩余元素处理流程，完全没完成两个子数组的归并比较，自然无法正确排序数组。同时还存在一个细节错误：归并比较时误拿原数组arr的元素做判断，而非临时子数组L和R。

错误代码片段：

while (i < n1 && j < n2){
    if (arr[i] <= arr[j]){ // 错误：应该用L[i]和R[j]比较
        arr[k] = L[i];
        i++;
        k++;
    }
    else {
        arr[k] = R[j];
        j++;
        k++;
    }

    // 错误：两个剩余元素处理循环被嵌套在外层while内部
    while(i < n1){
        arr[k] = L[i];
        i++;
        k++;
    }

    while(j < n2){
        arr[k] = R[j];
        j++;
        k++;
    }
}

修复后的完整MergeSort类 #

class MergeSort{
    public static void mergeSort(int[] arr, int l, int h){
        if (l < h){
            int mid  = (l + h) / 2;
            mergeSort(arr, l ,mid);
            mergeSort(arr, mid + 1 , h);
            merge(arr, l, mid, h);
        }
    }

    public static void merge(int[] arr, int l, int mid, int h){
        int n1 = mid - l + 1;
        int n2 = h - mid;

        int[] L = new int[n1];
        int[] R = new int[n2];

        for (int p = 0; p < n1; p++){
            L[p] = arr[p + l];
        }

        for (int p = 0; p < n2; p++){
            R[p] = arr[p + mid + 1];
        }

        int k = l;
        int i = 0;
        int j = 0;

        // 先完成两个子数组的归并比较
        while (i < n1 && j < n2){
            if (L[i] <= R[j]){ // 修正：用临时子数组元素比较
                arr[k] = L[i];
                i++;
                k++;
            }
            else {
                arr[k] = R[j];
                j++;
                k++;
            }
        }

        // 处理L数组剩余元素（移到外层循环之后）
        while(i < n1){
            arr[k] = L[i];
            i++;
            k++;
        }

        // 处理R数组剩余元素（移到外层循环之后）
        while(j < n2){
            arr[k] = R[j];
            j++;
            k++;
        }
    }  
}

修复逻辑说明 #

1. 将两个处理剩余元素的while循环移到外层归并循环之后，确保先完成两个子数组的逐元素比较归并，再处理未遍历完的剩余元素。
2. 修正归并比较的对象：用临时子数组L和R的元素做判断，而非原数组arr的元素，避免取到未处理的错误值。

修复后，无论MergeSort类是单独存放还是和其他类合并在同一个文件中，都能正确对数组进行排序，进而正确计算出活动通知的数量。

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