Java实现归并排序的方法详解(包含递归+非递归)

聊归并排序，绕不开这个核心：分治思想。简单说，就两步：拆 —— 把一个数组从中间劈开，拆到只剩一个元素；并 —— 把有序的小块，两两合并，逐步合成完整的有序数组。结果很漂亮：时间复杂度稳定在O(n log n)，空间复杂度为O(n)，而且它是稳定排序 —— 相等元素不会打乱原本的相对顺序。先给结论，再拆解细节。

下面直接扔可直接运行的 Ja va 代码，一份是递归版（最经典），另一份是迭代版（无栈溢出，更适合生产）。两版的合并逻辑一模一样，区别只在拆分方式。

1. 递归版归并排序（最常用）

核心流程是什么？
1. 从中间把数组拆成左右两份。
2. 递归对左右子数组排序。
3. 把排好序的两个子数组合并成一个。

代码不难，但有几个小细节值得注意：比如 mid = left + (right - left) / 2 的写法防溢出，以及提前准备好一块临时数组，避免在递归层数深的时候反复创建。

public class MergeSort {

    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        int[] temp = new int[arr.length];
        sort(arr, 0, arr.length - 1, temp);
    }

    private static void sort(int[] arr, int left, int right, int[] temp) {
        if (left >= right) return;
        int mid = left + (right - left) / 2;
        sort(arr, left, mid, temp);
        sort(arr, mid + 1, right, temp);
        merge(arr, left, mid, right, temp);
    }

    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left, j = mid + 1, k = left;

        while (i <= mid && j <= right) {
            temp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
        }
        while (i <= mid) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];

        System.arraycopy(temp, left, arr, left, right - left + 1);
    }

    public static void main(String[] args) {
        int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
        System.out.println("排序前：");
        for (int num : arr) System.out.print(num + " ");

        mergeSort(arr);

        System.out.println("\n递归归并排序后：");
        for (int num : arr) System.out.print(num + " ");
    }
}

运行试试，输入输出一目了然。递归版最大的优点是代码简洁好理解，但如果数组特别大（比如几十万个元素），递归深度可能触发 StackOverflowError。这时候迭代版就上场了。

2. 非递归版归并排序（迭代实现）

迭代版是怎么玩的？思路很直接：从数组里最小的一对元素（子数组长度 = 1）开始，两两合并；然后子数组长度翻倍（1→2→4→8…），继续合并；直到整个数组有序。没有递归，也就不存在栈溢出的风险。

代码里有一个关键变量 mergeSize，它控制了每次合并的“块”大小。循环里不断向左向右找左、中、右边界，然后调用一模一样的 merge 方法。注意边界处理：右边界不能越界，如果只有左半边就不用合并。

public class MergeSortNonRecursive {

    public static void mergeSortNonRecursive(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        int n = arr.length;
        int[] temp = new int[n];
        int mergeSize = 1;

        while (mergeSize < n) {
            for (int left = 0; left < n; left += mergeSize * 2) {
                int mid = left + mergeSize - 1;
                int right = Math.min(left + mergeSize * 2 - 1, n - 1);

                if (mid >= right) break;

                merge(arr, left, mid, right, temp);
            }
            mergeSize *= 2;
        }
    }

    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left, j = mid + 1, k = left;

        while (i <= mid && j <= right) {
            temp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
        }
        while (i <= mid) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];

        System.arraycopy(temp, left, arr, left, right - left + 1);
    }

    public static void main(String[] args) {
        int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
        System.out.println("排序前：");
        for (int num : arr) System.out.print(num + " ");

        mergeSortNonRecursive(arr);

        System.out.println("\n非递归归并排序后：");
        for (int num : arr) System.out.print(num + " ");
    }
}

核心说明

再说两个关键的细节：

• merge 方法是归并排序的“灵魂”。两个版本用的 merge 完全一样——先比较左右两个有序区的当前元素，小的放临时数组，然后补齐剩余，最后整段拷贝回原数组。
• 稳定性不是偶然。因为 if (arr[i] <= arr[j]) 这个条件保证了当左右元素相等时，优先取左边的，所以相对顺序不会被打乱。这是稳定的本质。

总结

• 递归版：自上而下拆分，代码最简洁，适合学习理解和面试手写。
• 非递归版：自下而上合并，没有递归栈深度限制，适合生产环境的大数据量。
• 两个版本的时间复杂度都是 O(n log n)，空间复杂度都是 O(n)（临时数组）。
• 代码复制粘贴就能跑，结果直接打印，一目了然。

想深入理解归并排序，建议先从递归版入手，理解了拆分-合并的递归逻辑后，再看迭代版会豁然开朗。