Java 归并排序：稳定排序的"秩序守护者"

Java 归并排序：稳定排序的”秩序守护者”

分而治之的典范——拆到最小，再有序合并

引言

归并排序（Merge Sort）把数组拆成两半分别排好，再像合并有序链表一样合二为一。

最大优点：稳定 + 稳定 O(n log n)。代价是需要额外 O(n) 空间。

它是少数几个能保证最坏情况也是 O(n log n)的排序算法（不像快排最坏 O(n²)），也是链表排序的最优解（快排对链表不友好）。

这篇文章，我会把归并排序讲透：

用 ASCII 图演示”拆分”和”合并”的完整过程
推导为什么 mid = left + (right - left) / 2 防溢出
列出 4 个高频易错点（尤其是边界条件）
配套 LeetCode 148（链表归并排序）和剑指 Offer 51（逆序对）

1. 核心思想：拆到不能再拆，再合并回来

1.1 通俗理解

归并排序的精髓：先递归拆分，再归并合并。

想象你要整理一堆混在一起的扑克牌：

1. 把牌堆从中间分成两半
2. 左边那堆继续分两半
3. 右边那堆继续分两半
4. 直到每堆只剩 1 张牌（天然有序）
5. 两两合并，合并时按顺序选小的
6. 最终合成一个有序牌堆

1.2 ASCII 图解演示

以数组 [38, 27, 43, 3, 9, 82, 10] 为例：

拆分过程（自顶向下）：
                       [38, 27, 43, 3, 9, 82, 10]
                      /                          \
            [38, 27, 43, 3]                  [9, 82, 10]
            /          \                    /          \
        [38, 27]      [43, 3]          [9, 82]      [10]
        /     \       /     \          /     \        |
      [38]   [27]   [43]   [3]      [9]    [82]    [10]

合并过程（自底向上）：
      [38]   [27]   [43]   [3]      [9]    [82]    [10]
        \    /        \    /          \    /         |
        [27, 38]      [3, 43]        [9, 82]       [10]
            \          /                \          /
            [3, 27, 38, 43]          [9, 10, 82]
                      \                /
                  [3, 9, 10, 27, 38, 43, 82]

1.3 merge 的细节图解

以合并 [27, 38] 和 [3, 43] 为例：

左：[27, 38]  右：[3, 43]
temp: []

步骤 1：左指针 i=0（27），右指针 j=0（3）
  27 > 3 → temp = [3]，j++

步骤 2：i=0（27），j=1（43）
  27 < 43 → temp = [3, 27]，i++

步骤 3：i=1（38），j=1（43）
  38 < 43 → temp = [3, 27, 38]，i++

步骤 4：i=2（越界）→ 把右半部分剩余 [43] 全部搬入
  temp = [3, 27, 38, 43]

最后把 temp 拷贝回 arr[left..right]

1.4 三个关键观察

拆分是 O(log n) 层——每层递归深度增加 1
**每层合并是 O(n)**——n 个元素都要比较一次
总复杂度 = O(n) × O(log n) = O(n log n)

2. 完整 Java 实现

import java.util.Arrays;

public class MergeSort {
    /**
     * 归并排序入口
     */
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        mergeSort(arr, 0, arr.length - 1);
    }

    /**
     * 递归拆分
     */
    private static void mergeSort(int[] arr, int left, int right) {
        // 递归终止：区间只剩 0 或 1 个元素
        if (left >= right) {
            return;
        }
        // 防溢出写法（不用 (left + right) / 2）
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

    /**
     * 合并两个有序子数组 arr[left..mid] 和 arr[mid+1..right]
     */
    private static void merge(int[] arr, int left, int mid, int right) {
        // 创建临时数组
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;

        // 双指针合并
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        // 把剩余部分搬入
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        // 拷贝回原数组
        for (int p = 0; p < temp.length; p++) {
            arr[left + p] = temp[p];
        }
    }

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("排序前: " + Arrays.toString(arr));
        mergeSort(arr);
        System.out.println("排序后: " + Arrays.toString(arr));
    }
}

3. 复杂度证明

3.1 时间复杂度

**最坏/最好/平均都是 O(n log n)**——这是归并排序最强的特性。

数学推导：

递归树深度 = log₂ n
每层合并总次数 = n
T(n) = 2T(n/2) + O(n)
主定理：T(n) = O(n log n)

3.2 空间复杂度

临时数组 O(n)
递归调用栈 O(log n)
总空间复杂度 O(n)，不是原地排序

3.3 稳定性：稳定

merge 里 arr[i] <= arr[j]（带等号）
相同元素，左半部分的会先放入 temp
稳定排序

4. 四个高频易错点

易错点 1：mid 计算溢出

// ❌ 错误：left + right 在大数组时可能溢出 int
int mid = (left + right) / 2;

// ✅ 正确：防溢出写法
int mid = left + (right - left) / 2;

原理：left + right 最大值约 4×10⁹，接近 Integer.MAX_VALUE（2.1×10⁹）时会溢出成负数。

易错点 2：递归终止写成 `left > right`

// ❌ 错误：left == right 时还会继续递归
if (left > right) {
    return;
}

// ✅ 正确：left == right 时区间只剩 1 个元素，已有序
if (left >= right) {
    return;
}

易错点 3：merge 时漏掉剩余部分

// ❌ 错误：i 或 j 越界后剩余元素丢失
while (i <= mid && j <= right) {
    if (arr[i] <= arr[j]) temp[k++] = arr[i++];
    else temp[k++] = arr[j++];
}
// 漏掉了 while (i <= mid) 和 while (j <= right)

// ✅ 正确：必须补完剩余部分
while (i <= mid && j <= right) { ... }
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];

易错点 4：temp 数组每次新建

// ⚠️ 不是 bug，但浪费内存（每次 merge 都 new 一个）
int[] temp = new int[right - left + 1];

// ✅ 优化：把 temp 提到 mergeSort 入口，每层递归复用
private static void mergeSort(int[] arr, int left, int right, int[] temp) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid, temp);
    mergeSort(arr, mid + 1, right, temp);
    merge(arr, left, mid, right, temp);
}

进阶优化：还可以改成自底向上的迭代版（适合链表）。

5. 三个进阶优化

优化 1：小数组切插入排序

private static void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return;
    // 小数组用插入排序（提升常数因子）
    if (right - left <= 16) {
        insertionSort(arr, left, right);
        return;
    }
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    // 优化：左边最大 <= 右边最小，无需合并
    if (arr[mid] <= arr[mid + 1]) return;
    merge(arr, left, mid, right);
}

优化 2：自底向上（迭代版）

public static void mergeSortIterative(int[] arr) {
    int n = arr.length;
    // step = 1, 2, 4, 8, ...
    for (int step = 1; step < n; step *= 2) {
        for (int left = 0; left + step < n; left += 2 * step) {
            int mid = left + step - 1;
            int right = Math.min(left + 2 * step - 1, n - 1);
            merge(arr, left, mid, right);
        }
    }
}

优点：无递归，栈空间 O(1)；适合链表（链表 merge 时改指针即可）。

优化 3：原地归并（理论可行，工程不推荐）

理论上可以用旋转操作实现 O(1) 空间，但实现复杂且常数大。工程上不推荐。

6. 适用场景与禁区

6.1 适用场景

需要稳定排序：归并是稳定 + O(n log n) 的唯一选择
链表排序：快排对链表不友好，归并是链表最优解
外部排序：数据太大装不进内存，分块读入后归并（如数据库排序）
最坏情况敏感：快排最坏 O(n²)，归并永远 O(n log n)

6.2 不适用场景

内存受限：O(n) 额外空间是硬伤
近乎有序的小数组：插入排序更快
随机访问密集：归并的连续搬移对缓存不友好

7. 面试常见变形

变形 1：自底向上归并（链表版）

链表 merge：改指针，不创建新节点

public ListNode mergeSortList(ListNode head) {
    if (head == null || head.next == null) return head;
    // 快慢指针找中点
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode mid = slow.next;
    slow.next = null;
    // 递归排序两半
    ListNode left = mergeSortList(head);
    ListNode right = mergeSortList(mid);
    // 合并
    return mergeTwoLists(left, right);
}

private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }
    curr.next = l1 != null ? l1 : l2;
    return dummy.next;
}

变形 2：求逆序对（剑指 Offer 51）

思路：merge 时统计”左边 > 右边”的对数

private static int count = 0;

public static int reversePairs(int[] arr) {
    count = 0;
    mergeSort(arr, 0, arr.length - 1);
    return count;
}

private static void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            // 关键：arr[i] > arr[j]，i 到 mid 都和 arr[j] 构成逆序对
            count += (mid - i + 1);
            temp[k++] = arr[j++];
        }
    }
    // ... 剩余部分同上
}

复杂度：O(n log n)。

变形 3：小和 + 大和

类似逆序对，merge 时统计”右边 > 左边”或”右边 < 左边”的对数。

8. LeetCode 真题实战

题目 1：148. 排序链表（中等）

描述：给你链表的头节点 head，请将其按升序排列并返回排序后的链表。

解法：套用变形 1 的链表归并模板。

复杂度：时间 O(n log n)，空间 O(log n)（递归栈）。

关键点：快慢指针找中点要写对——slow = head, fast = head.next（不是 head），否则中点偏右。

题目 2：912. 排序数组（中等）

归并解法：直接套用模板，能 AC。

注意：Java 提交时记得用 int[] temp = new int[n] 在入口处一次性分配，避免每次 merge 都 new。

题目 3：剑指 Offer 51. 数组中的逆序对（困难）

解法：套用变形 2。

复杂度：O(n log n)。

总结

一句话精髓

归并 = 拆到 1 个 + 合并有序 + 用 temp 数组。

三个关键洞察

稳定 + O(n log n) + 链表友好——三大独特优势
mid 防溢出是大厂高频坑——(left + right) / 2 早晚翻车
JDK Arrays.sort() 对对象数组用归并——因为对象排序要求稳定

下一步行动

手写链表归并排序（变形 1），理解”快慢指针找中点”的细节
用归并解剑指 Offer 51（逆序对），体会 merge 的扩展用法
在 OpenJDK 源码搜索 MergeSort，看 ComparableTimSort 的工业实现

本文由 AI 对话整理精炼而成
整理时间：2026-06-18
原文来源：DeepSeek

技术

#Java #算法 #排序 #归并排序 #分治

0 次浏览

Java 归并排序：稳定排序的"秩序守护者"

https://easyscreen.icu/2026/06/18/java-gui-bing-pai-xu-wen-ding-pai-xu-de-zhi-xu-shou-hu-zhe/

作者

杰哥

发布于

2026年6月18日

许可协议

Java 快速排序：分治思想的最强代表上一篇

Java堆排序：用二叉树思维排序下一篇

Java 归并排序：稳定排序的"秩序守护者"

Java 归并排序：稳定排序的”秩序守护者”

引言

1. 核心思想：拆到不能再拆，再合并回来

1.1 通俗理解

1.2 ASCII 图解演示

1.3 merge 的细节图解

1.4 三个关键观察

2. 完整 Java 实现

3. 复杂度证明

3.1 时间复杂度

3.2 空间复杂度

3.3 稳定性：稳定

4. 四个高频易错点

易错点 1：mid 计算溢出

易错点 2：递归终止写成 left > right

易错点 3：merge 时漏掉剩余部分

易错点 4：temp 数组每次新建

5. 三个进阶优化

优化 1：小数组切插入排序

优化 2：自底向上（迭代版）

优化 3：原地归并（理论可行，工程不推荐）

6. 适用场景与禁区

6.1 适用场景

6.2 不适用场景

7. 面试常见变形

变形 1：自底向上归并（链表版）

变形 2：求逆序对（剑指 Offer 51）

变形 3：小和 + 大和

8. LeetCode 真题实战

题目 1：148. 排序链表（中等）

题目 2：912. 排序数组（中等）

题目 3：剑指 Offer 51. 数组中的逆序对（困难）

总结

一句话精髓

三个关键洞察

下一步行动

易错点 2：递归终止写成 `left > right`