核心思想#

分治法（Divide and Conquer）：

1. 分解：将数组从中间一分为二
2. 递归求解：对左右子数组递归地进行归并排序
3. 合并：将两个已排序子数组合并为一个有序数组

1
原始: [8,4,5,7,1,3,6,2]
2
分解: [8,4,5,7]        [1,3,6,2]
3
      [8,4] [5,7]      [1,3] [6,2]
4
      [8][4] [5][7]    [1][3] [6][2]
5
合并: [4,8] [5,7]      [1,3] [2,6]
6
      [4,5,7,8]        [1,2,3,6]
7
      [1,2,3,4,5,6,7,8]

代码实现#

1
int *B = (int *)malloc((n + 1) * sizeof(int));
2

3
void Merge(int A[], int low, int mid, int high) {
4
    int i, j, k;
5
    for (k = low; k <= high; k++)
6
        B[k] = A[k];
7
    for (i = low, j = mid + 1, k = low; i <= mid && j <= high; k++) {
8
        if (B[i] <= B[j])    // ⭐ <= 保证稳定性
9
            A[k] = B[i++];
10
        else
11
            A[k] = B[j++];
12
    }
13
    while (i <= mid)  A[k++] = B[i++];
14
    while (j <= high) A[k++] = B[j++];
15
}

1
void MergeSort(int A[], int low, int high) {
2
    if (low < high) {
3
        int mid = (low + high) / 2;
4
        MergeSort(A, low, mid);
5
        MergeSort(A, mid + 1, high);
6
        Merge(A, low, mid, high);
7
    }
8
}

递归分析#

• 第 1 层：1 个长度为 n 的序列
• 第 2 层：2 个长度为 n/2 的序列
• 第 k 层：2^(k-1) 个长度为 n/2^(k-1) 的序列
• 共 ⌈log₂n⌉ 层（归并趟数）

每层归并操作总共 O(n)，总时间 O(n log n)。

复杂度#

⚠️ 易错：归并排序的每一趟是对相邻有序子表两两合并。第 1 趟后每子表长 2，第 2 趟后长 4……第 k 趟后长 2^k。

与快速排序对比#

考研高频考点#

• ⭐ 时间复杂度：所有情况均为 O(n log n)
• ⭐ 空间复杂度 O(n)：需与原数组等长辅助数组
• ⭐ 归并趟数 ⌈log₂n⌉
• ⭐ 是稳定的排序算法
• ⭐ 归并排序 vs 快速排序的对比
• Merge 操作 <= 保证稳定性的细节
• 每趟归并的比较次数分析

关联页面#

• 排序基础概念 — 算法总览、稳定性
• 交换排序 — 快速排序（归并 vs 快排对比）
• 选择排序 — 堆排序（归并 vs 堆排对比）
• 外部排序 — 外部排序基于归并思想
• 排序资料摘要