我无法弄清楚这个合并排序算法的问题

Question

我正在尝试学习数据结构和算法，我很享受这个过程。我开始研究合并排序的工作原理并想要实现它。这是我的代码，出于某种原因我无法弄清楚为什么我的输出混乱！

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 ele : new_list) {
            System.out.print(ele + " ");
        }
        System.out.println();
    }

    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);
    }

这是我的输出，（打印合并函数的每个调用）：

10 25 
3 50 
3 25 10 50 
14 24 
8 22 
8 22 24 14 
24 14 8 22 25 10 3 50 
35 42 
5 10 
10 5 35 42 
18 29 
18 29 50 
18 29 35 42 10 5 50 
25 10 3 35 42 10 5 18 29 50 24 14 8 22 50

我在这里做错了什么？我尝试询问 chatGPT，得到的答复是它无法从给定的代码中找到任何错误！

我尝试在 python 上重写整个代码，并发现列表在插入到新“排序”数组中时未正确排序。但我不知道如何解决这个问题。

Answer 1

您的代码看起来几乎正确，您只是没有用排序的元素更新原始数组。将元素合并到新的数组中后，您需要将它们复制回原始数组中。我已经测试了你的代码，在最后添加这个循环后它看起来是正确的：

    for (int i = 0; i < new_list.size(); i++)
        arr.set(low + i, new_list.get(i));