递归归并排序实现求助：代码运行后始终提示未正确排序

你的代码存在两个核心问题，直接导致排序失效：

1. 缺失递归排序子数组的关键步骤 #

归并排序的核心逻辑是分治：先拆分数组为子数组，递归排序每个子数组，再合并排序后的结果。但你的代码拆分出arr1和arr2后，直接进行合并操作，没有先对这两个子数组调用mergesort排序，合并的是未排序的原始子数组，结果自然错误。

2. 合并结果未写回原数组 #

你创建了merge数组存储合并后的有序数据，但没有将merge的内容复制回原数组arr，导致原数组start在调用mergesort后完全没有被修改，和Arrays.sort处理后的数组必然不相等。

修复后的完整代码 #

import java.util.Arrays;

public class MergeSort {

    public static void main(String[] args) {
        int[] start = new int[100];
        for(int i = 0; i < start.length; i++) {
            start[i] = (int)(Math.random()*20 + 1);
        }
        int[] sorted = Arrays.copyOf(start, start.length);
        Arrays.sort(sorted);
        mergesort(start);
        if(Arrays.equals(start, sorted))
            System.out.print("correctly sorted");
        else
            System.out.print("not properly sorted");
    }
    
    public static void mergesort(int[] arr) {
        // 基准情况：数组长度<=1无需排序
        if(arr.length <= 1) {
            return;
        }
        // 拆分数组
        int half = arr.length / 2;
        int[] arr1 = new int[half];
        for(int i = 0; i < half; i++) {
            arr1[i] = arr[i];
        }
        int[] arr2 = new int[arr.length - half];
        for(int i = half; i < arr.length; i++) {
            arr2[i - half] = arr[i];
        }

        // 递归排序两个子数组
        mergesort(arr1);
        mergesort(arr2);

        // 合并排序后的子数组，直接写入原数组
        int k = 0;
        int i = 0;
        int j = 0;
        while(i < arr1.length && j < arr2.length) {
            if(arr1[i] <= arr2[j]) {
                arr[k++] = arr1[i++];
            } else {
                arr[k++] = arr2[j++];
            }
        }
        // 处理剩余未合并的元素
        while(i < arr1.length) {
            arr[k++] = arr1[i++];
        }
        while(j < arr2.length) {
            arr[k++] = arr2[j++];
        }
    }
}

额外优化说明 #

• 基准条件简化为if(arr.length <= 1)，原代码中arr.length ==0 || arr.length <2 || arr.length <=1存在重复冗余。
• 合并循环的条件做了简化：外层循环已经保证i<arr1.length && j<arr2.length，无需额外判断j>=arr2.length。

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