DS-07-06 归并排序

408 > ### 数据结构 > #### 归并排序（二路归并）

---

一、定位信息

维度	内容
章节归属	第7章 排序
知识单元编号	DS-07-06
前置知识	DS-07-01 排序基本概念、分治思想
后续衔接	DS-07-08 外部排序（多路归并）、DS-07-09 综合对比
考试大纲要求	掌握归并排序的算法思想、实现及性能分析
预计学习时长	40分钟

---

二、知识点讲解

1. 基本思想

归并排序（Merge Sort）是分治法在排序中的又一经典应用。其核心思想是：

1. 分解（Divide）：将待排序序列从中间分成两个子序列
2. 递归（Conquer）：对两个子序列分别递归进行归并排序
3. 合并（Combine）：将两个已有序的子序列合并为一个有序序列

二路归并：每次将两个有序子序列合并为一个有序序列。

2. 合并操作（核心）

合并操作是归并排序的基本操作——将两个有序序列合并为一个有序序列。

void Merge(ElementType A[], int low, int mid, int high) {
    // 将 A[low..mid] 和 A[mid+1..high] 两个有序子序列合并
    // 结果存回 A[low..high]
    ElementType *temp = (ElementType *)malloc((high - low + 1) * sizeof(ElementType));
    int i = low;      // 左子序列的指针
    int j = mid + 1;  // 右子序列的指针
    int k = 0;        // 临时数组的指针

    // 两个子序列都未取完时，取较小者放入临时数组
    while (i <= mid && j <= high) {
        if (A[i].key <= A[j].key) {  // 注意：用 <= 保证稳定性
            temp[k++] = A[i++];
        } else {
            temp[k++] = A[j++];
        }
    }

    // 将剩余元素拷贝到临时数组
    while (i <= mid) temp[k++] = A[i++];
    while (j <= high) temp[k++] = A[j++];

    // 将临时数组拷贝回原数组
    for (k = 0; k < high - low + 1; k++) {
        A[low + k] = temp[k];
    }

    free(temp);  // 释放临时空间
}

3. 归并排序递归实现

void MergeSort(ElementType A[], int low, int high) {
    // 对 A[low..high] 进行归并排序
    if (low < high) {          // 至少两个元素才需要排序
        int mid = (low + high) / 2;  // 从中间划分
        MergeSort(A, low, mid);      // 递归排左半部分
        MergeSort(A, mid + 1, high); // 递归排右半部分
        Merge(A, low, mid, high);    // 合并两个有序子序列
    }
}

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

void MergeSortNonRecursive(ElementType A[], int n) {
    // 非递归归并排序
    int size = 1;  // 当前子序列的长度
    while (size < n) {
        for (int i = 0; i < n; i += 2 * size) {
            // 合并 A[i..i+size-1] 和 A[i+size..i+2*size-1]
            int low = i;
            int mid = min(i + size - 1, n - 1);
            int high = min(i + 2 * size - 1, n - 1);
            if (mid < high)  // 有右子序列才需要合并
                Merge(A, low, mid, high);
        }
        size *= 2;  // 子序列长度翻倍
    }
}

5. 时间复杂度分析

5.1 递推关系

设 T(n) 为对 n 个元素归并排序的时间：

• 分解：O(1)（计算 mid）
• 递归：2T(n/2)（对两个子序列递归排序）
• 合并：O(n)（合并两个有序子序列，需比较 n-1 次，移动 n 次）

递推式：T(n) = 2T(n/2) + O(n)

5.2 求解

由主定理（Master Theorem）：a=2, b=2, f(n)=n

• n^{log_b(a)} = n^1 = n = f(n)
• 属于情况 2：T(n) = O(n log n)

情况	时间复杂度	说明
最好	O(n log n)	分解层次和合并代价不变
最坏	O(n log n)	同上
平均	O(n log n)	同上

关键特征：归并排序的时间复杂度与初始序列无关，始终为 O(n log n)。

5.3 详细分析

递归树共 log₂n 层，每层合并的总代价为 O(n)：

• 第 0 层：1 次合并，合并 n 个元素，代价 O(n)
• 第 1 层：2 次合并，每次合并 n/2 个元素，总代价 O(n)
• …
• 第 k 层：2^k 次合并，每次合并 n/2^k 个元素，总代价 O(n)

总代价 = O(n) × log₂n = O(n log n)

6. 空间复杂度

• 递归版本：O(n + log n) = O(n)。其中 O(n) 用于 Merge 操作的辅助数组，O(log n) 用于递归栈
• 非递归版本：O(n)。仅需辅助数组

归并排序不是原地排序，需要额外的 O(n) 空间。这是归并排序的主要缺点。

7. 稳定性

稳定。合并时当两个子序列关键字相等时，A[i].key <= A[j].key 条件保证优先取前半部分元素，维持了原顺序。

---

8. 归并排序 vs 其他 O(n log n) 排序 对比表

对比维度	归并排序	快速排序	堆排序
时间（最好）	O(n log n)	O(n log n)	O(n log n)
时间（最坏）	O(n log n)	O(n²)	O(n log n)
时间（平均）	O(n log n)	O(n log n)	O(n log n)
空间复杂度	O(n)	O(log n)	O(1)
稳定性	稳定	不稳定	不稳定
适用场景	需要稳定排序	通用首选	空间受限

---

三、记忆辅助

1. 归并 = 分治 + 合并：分到只剩一个元素，然后两两合并，像"两两配对比赛"
2. 时间 O(n log n) 恒定：不管初始序列如何，归并排序始终 O(n log n)——这是它的核心优势
3. 空间 O(n) 是代价：稳定 + 最坏 O(n log n) 的代价就是需要额外空间
4. 稳定性的保证：合并时 <= 条件优先取前半部分，关键字相等时不改变顺序
5. 外排的基础：外部排序的核心就是多路归并，归并排序是外排的基础

---

四、例题精解

例题 1：归并排序过程模拟

题目：对序列 (4, 8, 2, 7, 1, 5, 3, 6) 进行二路归并排序，画出递归树并写出最终排序过程。

第一步：审题 n=8，需要展示递归分解和合并的完整过程。

第二步：递归分解过程

                    [4,8,2,7,1,5,3,6]
                   /                 \
            [4,8,2,7]            [1,5,3,6]
           /        \            /        \
        [4,8]      [2,7]     [1,5]      [3,6]
        /   \      /   \      /   \      /   \
      [4]  [8]  [2]  [7]  [1]  [5]  [3]  [6]

合并过程（自底向上）：

第 1 层合并（子序列长度 1→2）：

• [4]+[8] → [4,8]
• [2]+[7] → [2,7]
• [1]+[5] → [1,5]
• [3]+[6] → [3,6]

第 2 层合并（子序列长度 2→4）：

• [4,8]+[2,7] → [2,4,7,8]
• [1,5]+[3,6] → [1,3,5,6]

第 3 层合并（子序列长度 4→8）：

• [2,4,7,8]+[1,3,5,6] → [1,2,3,4,5,6,7,8]

第三步：解答 最终有序序列：[1, 2, 3, 4, 5, 6, 7, 8]

第四步：总结 归并排序的递归树是完全二叉树，高度为 ⌈log₂n⌉ = 3。每层合并的总比较次数为 O(n)，总时间复杂度为 O(n log n)。

---

例题 2：归并排序的空间复杂度分析

题目：归并排序为什么需要 O(n) 的额外空间？能否改进到 O(1)？

第一步：审题 分析归并排序空间消耗的来源，以及是否可能原地归并。

第二步：分析

空间消耗有两个来源：

1. 辅助数组：Merge 操作需要一个临时数组存放合并结果，大小为 O(n)
2. 递归栈：递归版本的调用栈深度为 O(log n)

总空间 = O(n) + O(log n) = O(n)

能否改进到 O(1)？

• 原地归并算法存在（如 block merge sort），但非常复杂，常数因子大
• 实际中一般不使用原地归并，因为 O(n) 空间代价通常可接受

第三步：解答 归并排序需要 O(n) 辅助空间的原因是：合并两个有序子序列时，需要临时空间存放合并结果。虽然存在原地归并算法（如 block merge），但实现复杂、常数因子大，实际中很少使用。

第四步：总结 归并排序以 O(n) 空间换取了稳定的 O(n log n) 时间。在空间不是瓶颈的场景下（如外部排序），归并排序是首选。

---

例题 3：合并两个有序序列的比较次数

题目：将两个长度分别为 m 和 n 的有序序列合并，最少和最多各需多少次比较？

第一步：审题 分析合并操作的比较次数范围。

第二步：分析

最少比较次数：当一个序列的最大值 ≤ 另一个序列的最小值时

• 如 (1,2,3) 和 (4,5,6)，只需比较 3 次（每次 A[i] < A[j]，取 A[i]）
• 最少比较次数 = min(m, n)

最多比较次数：当两个序列交替大于对方时

• 如 (1,3,5) 和 (2,4,6)，每步都需要比较
• 最多比较次数 = m + n - 1（最后一次不需要比较，因为只剩一个序列有剩余）

第三步：解答

• 最少比较次数：min(m, n)
• 最多比较次数：m + n - 1

第四步：总结 合并操作的比较次数取决于两个序列的交错程度。归并排序中每层合并的总比较次数为 O(n)，这是归并排序总时间复杂度为 O(n log n) 的关键。

---

五、考情分析

年份	题型	考点	难度
高频	分析题	归并排序的递归过程	★★★
高频	选择题	归并排序的空间复杂度	★★☆
中频	应用题	合并操作的比较次数分析	★★★
低频	选择题	归并排序的稳定性	★★☆

命题趋势：

• 归并排序是 408 的高频考点，常以分析题考查递归过程
• 空间复杂度是选择题常考点
• 与外部排序结合考查（多路归并）
• 有时考查非递归版本的实现

---

六、易错点

1. 归并排序的空间复杂度是 O(n)：不是 O(1)，不是 O(log n)。辅助数组占 O(n)，递归栈占 O(log n)
2. 合并时的等号处理：A[i].key <= A[j].key 用 <= 而非 <，这是保证稳定性的关键
3. 归并排序始终 O(n log n)：不存在 O(n²) 的最坏情况，这与快排不同
4. 递归终止条件：是 low < high（至少两个元素），不是 low <= high
5. 合并操作的临时空间：每次合并都需要分配和释放，或者使用全局辅助数组

---

七、来源标注

• 《数据结构（C语言版）》严蔚敏，第10.5节 归并排序
• 《数据结构》王道考研，第7章 7.5节 归并排序
• 408考试大纲：数据结构部分-归并排序
• 《算法导论》Thomas H. Cormen，第2.3节 归并排序