Java归并排序（MergeSort）算法代码中文翻译与技术说明需求

先给大家补上完整可运行的代码（原代码的merge方法未写完，我补充了标准实现）：

public class mergesort { 
    public static int[] mergesort (int[] input) { 
        int length = input.length; 
        // 基线条件：数组长度≤1时，本身就是有序的，直接返回
        if (length <= 1) { 
            return input; 
        } 
        // 计算拆分点，把数组分成左右两部分
        int median = length/2; 
        int[] left = new int[median]; 
        int[] right = new int[length-median]; 
        // 把原数组前半部分复制到left数组
        for (int x = 0; x< median; x++) { 
            left[x] = input[x]; 
        } 
        // 把原数组后半部分复制到right数组，y-median是为了让right从索引0开始填充
        for (int y = median; y < length; y++) { 
            right[y-median] = input[y]; 
        } 
        // 递归拆分左右子数组，直到子数组长度≤1
        mergesort(left); 
        mergesort(right); 
        // 合并两个已经有序的子数组到原数组
        merge(left, right, input); 
        return input; 
    } 
    // 合并两个有序子数组的核心方法
    public static int[] merge (int[] left, int[] right, int[] input) {
        // i遍历left，j遍历right，k负责填充原数组input
        int i = 0, j = 0, k = 0;
        // 同时遍历两个子数组，每次取较小的元素放入input
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                input[k++] = left[i++];
            } else {
                input[k++] = right[j++];
            }
        }
        // 处理left数组剩下的元素（如果有的话）
        while (i < left.length) {
            input[k++] = left[i++];
        }
        // 处理right数组剩下的元素（如果有的话）
        while (j < right.length) {
            input[k++] = right[j++];
        }
        return input;
    }
}

逐段代码解释 #

1. 递归拆分的核心方法：mergesort #

这个方法是归并排序的「拆分环节」，采用经典的分治思想：

• 终止条件判断：当数组长度≤1时，单个元素本身就是有序的，直接返回——这是递归的终点，避免无限递归。
• 拆分数组：通过length/2计算拆分点，把原数组分成左右两个子数组。这里用整数除法，比如长度为5的数组，拆分点是2，左数组长度2，右数组长度3。
• 填充子数组：用两个循环分别把原数组的前后部分复制到左右子数组里，第二个循环的y-median是为了让right数组从索引0开始填充，不然直接用y的话会触发数组越界。
• 递归+合并：先递归拆分左右子数组，直到每个子数组都只剩单个元素，然后调用merge方法把这些有序子数组合并起来，最后返回排序好的原数组。

2. 合并有序数组的方法：merge #

这个方法是归并排序的「合并环节」，也是算法的核心：

• 指针初始化：三个指针分别负责遍历左子数组、右子数组，以及填充原数组。
• 双指针合并：同时遍历两个有序子数组，每次挑出较小的元素放到原数组里，然后移动对应的指针。这样能保证合并后的数组始终保持有序。
• 处理剩余元素：当其中一个子数组遍历完后，另一个子数组剩下的元素肯定都是大于等于已经合并的元素（因为子数组本身有序），所以直接把剩余元素依次追加到原数组末尾就行。

归并排序的时间复杂度是O(n log n)，属于稳定排序算法，适合处理大规模数据排序，不过需要额外的空间来存储子数组，空间复杂度是O(n)。

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