归并排序

归并排序（Merge Sort）是一种基于分治思想的高效排序算法。其核心思想包括以下几个步骤：

1. 分解（Divide）：将待排序的数组分成两个子数组，每个子数组包含大约一半的元素
2. 解决（Conquer）：递归地对每个子数组进行排序
3. 合并（Combine）：将两个已排序的子数组合并成一个有序的数组

graph TD
  A[原数组] --> B[分左半]
  A --> C[分右半]
  B --> D[继续二分]
  C --> E[继续二分]
  D --> F[长度1 有序]
  E --> G[长度1 有序]
  F --> H[合并]
  G --> H

一、算法流程图解

以数组 [38, 27, 43, 3, 9, 82, 10] 为例，归并排序的完整过程如下：

分解阶段（自顶向下，不断二分直到子数组长度为 1）：

                    [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]

合并阶段（自底向上，两两归并有序子数组）：

 [27, 38]      [3, 43]            [9, 82]       [10]
      \         /                      \         /
   [3, 27, 38, 43]                  [9, 10, 82]
            \                          /
      [3, 9, 10, 27, 38, 43, 82]

合并操作的核心逻辑——双指针逐个比较：

左: [27, 38]    右: [3, 43]    结果: []
     i                j

比较 27 vs 3  → 取 3   → 结果: [3]
比较 27 vs 43 → 取 27  → 结果: [3, 27]
比较 38 vs 43 → 取 38  → 结果: [3, 27, 38]
左边耗尽，追加右边剩余  → 结果: [3, 27, 38, 43]

二、时间复杂度分析

• 分解：将数组分成两半，直到每个子数组只有一个元素。递归深度为 O(log n)
• 合并：每一层的所有合并操作总共处理 n 个元素，每层耗时 O(n)

总工作量 = 层数 × 每层工作量 = O(log n) × O(n) = O(n log n)

用递推公式严格证明：

T(n) = 2T(n/2) + O(n)
     = 2(2T(n/4) + O(n/2)) + O(n) = 4T(n/4) + 2·O(n)
     = ...
     = n·T(1) + O(n log n)
     = O(n log n)

关键特性：无论输入数据是有序、逆序还是随机，归并排序的时间复杂度恒定为 O(n log n)，不存在最坏情况退化。这是它与快速排序（最坏 O(n²)）的本质区别。

三、空间复杂度

归并排序在合并过程中需要额外的空间来存储临时数组。因此归并排序的空间复杂度是 O(n)。

具体分析：

• 递归版本：临时数组 O(n) + 递归调用栈 O(log n) → 总计 O(n)
• 迭代版本（自底向上）：临时数组 O(n)，无递归栈 → 总计 O(n)
• 链表版本：只需要 O(log n) 的递归栈（迭代版可做到 O(1)）

四、稳定性

归并排序是一种稳定的排序算法，因为在合并过程中，当两个元素相等时，优先选择左边子数组中的元素（使用 <= 比较），这样可以保持相等元素的相对顺序。

// 稳定性的关键：相等时取左边
if (temp[i].compareTo(temp[j]) <= 0) {  // <= 保证稳定
    arr[k] = temp[i++];
} else {
    arr[k] = temp[j++];
}

如果将 <= 改为 <，相等时会优先取右边元素，排序就变成不稳定的了。

五、代码实现（递归版）

public class MergeSort {

    public static <E extends Comparable<E>> void sort(E[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private static <E extends Comparable<E>> void sort(E[] arr, int l, int r) {
        if (l >= r) return;
        int mid = l + (r - l) / 2;
        sort(arr, l, mid);
        sort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }

    private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r) {
        E[] temp = Arrays.copyOfRange(arr, l, r + 1);
        int i = l, j = mid + 1;
        for (int k = l; k <= r; k++) {
            if (i > mid) { arr[k] = temp[j - l]; j++; }
            else if (j > r) { arr[k] = temp[i - l]; i++; }
            else if (temp[i - l].compareTo(temp[j - l]) <= 0) { arr[k] = temp[i - l]; i++; }
            else { arr[k] = temp[j - l]; j++; }
        }
    }
}

六、自底向上迭代版

递归版本存在调用栈开销，且对超大数据可能栈溢出。自底向上版本用循环替代递归：从长度为 1 的子数组开始，每轮将相邻的两个有序段合并，段长翻倍，直到整个数组有序。

public class MergeSortBU {

    public static <E extends Comparable<E>> void sort(E[] arr) {
        int n = arr.length;
        for (int size = 1; size < n; size *= 2) {
            for (int lo = 0; lo < n - size; lo += 2 * size) {
                int mid = lo + size - 1;
                int hi = Math.min(lo + 2 * size - 1, n - 1);
                merge(arr, lo, mid, hi);
            }
        }
    }

    private static <E extends Comparable<E>> void merge(E[] arr, int lo, int mid, int hi) {
        E[] temp = Arrays.copyOfRange(arr, lo, hi + 1);
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid) { arr[k] = temp[j - lo]; j++; }
            else if (j > hi) { arr[k] = temp[i - lo]; i++; }
            else if (temp[i - lo].compareTo(temp[j - lo]) <= 0) { arr[k] = temp[i - lo]; i++; }
            else { arr[k] = temp[j - lo]; j++; }
        }
    }
}

迭代版的执行过程（以 [5, 2, 4, 1] 为例）：

size=1: [5,2] → [2,5]    [4,1] → [1,4]    → [2,5,1,4]
size=2: [2,5,1,4] → 合并 → [1,2,4,5]      → 完成

七、链表上的归并排序

归并排序是链表排序的最优选择：链表不支持随机访问（快排的 partition 效率退化），但归并只需要顺序遍历和指针拼接，可以做到 O(1) 额外空间。

public class LinkedListMergeSort {

    public ListNode sortList(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 = sortList(head);
        ListNode right = sortList(mid);
        return mergeTwoLists(left, right);
    }

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

链表 vs 数组归并的差异：

八、经典应用：统计逆序对

归并排序最重要的衍生应用是统计逆序对（LeetCode 剑指 Offer 51 / LC 315 的基础）。逆序对定义：若 i < j 且 arr[i] > arr[j]，则 (i, j) 是一个逆序对。

核心洞察：在合并阶段，当右边元素 temp[j] 先于左边元素 temp[i] 被放入结果时，temp[j] 与左边剩余的所有元素（mid - i + 1 个）都构成逆序对。

public class ReversePairs {

    public int reversePairs(int[] nums) {
        return sort(nums, 0, nums.length - 1);
    }

    private int sort(int[] arr, int l, int r) {
        if (l >= r) return 0;
        int mid = l + (r - l) / 2;
        int count = sort(arr, l, mid) + sort(arr, mid + 1, r);
        // 合并时统计跨越左右的逆序对
        int[] temp = Arrays.copyOfRange(arr, l, r + 1);
        int i = l, j = mid + 1;
        for (int k = l; k <= r; k++) {
            if (i > mid) { arr[k] = temp[j - l]; j++; }
            else if (j > r) { arr[k] = temp[i - l]; i++; }
            else if (temp[i - l] <= temp[j - l]) { arr[k] = temp[i - l]; i++; }
            else {
                arr[k] = temp[j - l]; j++;
                count += mid - i + 1;  // 关键：左边剩余元素都比 temp[j] 大
            }
        }
        return count;
    }
}

为什么是 O(n log n)：暴力枚举需要 O(n²) 对 (i, j) 逐一检查；归并法在排序过程中"顺便"统计，每一层合并只增加 O(n) 的计数操作。

九、归并排序 vs 快速排序

选择建议：

• 需要稳定性 → 归并排序（或其改进 TimSort）
• 内存敏感、原地排序 → 快速排序
• 链表数据 → 归并排序
• 数据量超出内存 → 归并排序（外部排序）
• 通用场景追求极致速度 → 快速排序 / IntroSort

十、优化技巧

1. 近有序数组优化

在归并排序中，可以添加一个优化：如果 arr[mid] <= arr[mid + 1]，说明两个子数组已经有序，可以跳过合并操作。这个优化可以将近乎有序的数组排序时间降低到 O(n)。

private static void sort(int[] arr, int l, int r) {
    if (l >= r) return;
    int mid = l + (r - l) / 2;
    sort(arr, l, mid);
    sort(arr, mid + 1, r);
    if (arr[mid] > arr[mid + 1]) {  // 仅在不有序时才合并
        merge(arr, l, mid, r);
    }
}

2. 小数组切换插入排序

递归到底层时，子数组长度很小（如 ≤ 15），插入排序的常数因子远小于归并。混合策略可减少约 10%~15% 的运行时间：

private static void sort(int[] arr, int l, int r) {
    if (r - l <= 15) {
        insertionSort(arr, l, r);
        return;
    }
    // ... 正常归并逻辑
}

3. 复用临时数组

标准实现每次 merge 都分配新数组。可以在排序开始时分配一次全局辅助数组，交替使用两个数组作为源和目标，避免反复分配内存。Java 的 TimSort 就采用了这种策略。

十一、外部排序

当数据量超出内存容量时（如对 100GB 日志文件排序），归并排序是唯一实用的排序方案：

外部排序流程：

1. 分块（Run Generation）：每次读入内存能容纳的数据块（如 1GB），用内部排序（归并/快排）排好后写回磁盘
2. 多路归并（K-way Merge）：用大小为 K 的最小堆，从 K 个有序块中各取一个元素，每次弹出堆顶最小值写入输出
3. 多轮归并：如果有序块数量超过可同时打开的文件数，先分组归并减少块数，再进行下一轮

100GB 数据，内存 1GB：
第1步：生成 100 个 1GB 的有序块
第2步：100路归并（堆大小仅100个元素）
       每次从堆顶取最小值 → 输出有序结果

为什么不用快排：快排的 partition 需要随机访问数据，磁盘随机 IO 比顺序 IO 慢 1000 倍以上。归并排序对每个块只做顺序读写，天然适合磁盘。

十二、面试常见题

十三、易错点分析

1. mid 计算溢出

// ❌ 当 l + r 超过 int 范围时溢出
int mid = (l + r) / 2;
// ✅ 防溢出写法
int mid = l + (r - l) / 2;

2. 临时数组下标偏移

拷贝 arr[l..r] 到 temp[0..r-l] 后，访问原下标 i 对应的元素是 temp[i - l]，忘记减偏移量是最常见的 bug。

3. 稳定性破坏

合并时相等元素必须取左边的（<=），否则排序不稳定。面试中如果题目要求稳定排序，这一点必须明确说明。

4. 链表找中点的快指针起始位置

// ❌ fast = head：偶数长度时 slow 停在偏右中点，断开后左短右长，可能死循环
// ✅ fast = head.next：slow 停在偏左中点，保证左半部分 ≥ 右半部分
ListNode slow = head, fast = head.next;

5. 迭代版边界条件

lo < n - size 保证右半段至少有一个元素；hi = min(lo + 2*size - 1, n - 1) 防止越界。漏掉 min 会导致数组越界。