归并排序算法实现异常求助：输出结果混乱原因排查

你的归并排序实现核心问题在于合并阶段没有将排序后的结果写回原数组。Merge函数生成了排序好的临时列表new_list，但仅打印了它，没有把这些元素替换原数组arr中[low, high]区间的元素。这导致后续递归调用时，使用的还是未排序的原数组数据，最终输出混乱。

修复后的代码 #

修改Merge函数，在打印后添加将临时列表元素复制回原数组的逻辑：

public static void Merge(ArrayList<Integer> arr, int low, int mid, int high) {
    int left = low;
    int rightPointer = mid + 1;

    ArrayList<Integer> new_list = new ArrayList<>();

    while (left <= mid && rightPointer <= high) {
        if (arr.get(left) <= arr.get(rightPointer)) {
            new_list.add(arr.get(left));
            left++;
        } else {
            new_list.add(arr.get(rightPointer));
            rightPointer++;
        }
    }

    while (left <= mid) {
        new_list.add(arr.get(left));
        left++;
    }

    while (rightPointer <= high) {
        new_list.add(arr.get(rightPointer));
        rightPointer++;
    }

    // 关键：将排序后的结果写回原数组的对应区间
    for (int i = 0; i < new_list.size(); i++) {
        arr.set(low + i, new_list.get(i));
    }

    for (int ele : new_list) {
        System.out.print(ele + " ");
    }
    System.out.println();
}

// MergeSort和main函数保持不变
public static void MergeSort(ArrayList<Integer> arr, int low, int high) {
    if (low >= high)
        return;
    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) {
    ArrayList<Integer> list = new ArrayList<>(
            Arrays.asList(25, 10, 3, 50, 24, 14, 8, 22, 35, 42, 10, 5, 18, 29, 50));

    MergeSort(list, 0, list.size() - 1);
    // 打印最终排序后的数组
    System.out.println("最终排序结果：");
    for (int num : list) {
        System.out.print(num + " ");
    }
}

问题解释 #

你之前看到的Merge函数输出是临时列表的正确排序结果，但原数组并没有被更新。比如第一次合并[25,10]得到[10,25]，但原数组的这两个位置还是25,10，后续合并更大区间时，用的还是旧数据，自然会出现混乱的输出。

添加arr.set(low + i, new_list.get(i))后，每次合并的结果都会同步到原数组，递归过程中后续的拆分和合并都会基于已排序的子数组，最终得到正确的排序结果。

内容的提问来源于stack exchange，提问作者DineshK-1