归并排序

先排序两半，再合并

像整理两叠已经有序的卡片，每次取两叠顶端较小的一张，就能得到整体有序的序列。

对半划分直到区间长度不超过 1；左右递归完成后，从两边头部比较并写入临时数组，最后复制回原区间。每层合并共 O(n)，层数 O(log n)，总时间 O(n log n)，常见实现额外空间 O(n)。

相等时优先拿左侧元素，可以保持原先相同关键字的相对次序，因此归并排序可以稳定。下面用半开区间 [l,r)，这样长度就是 r−l。

为什么归并排序是 O(n log n)

对 [3, 1, 2, 1]，先拆成 [3, 1] 与 [2, 1]，再拆成单元素。合并后依次得到 [1, 3]、[1, 2]，最后得到 [1, 1, 2, 3]。

1. 每次把区间分成约一半，拆分深度是 O(log n)。
2. 同一合并层中，所有区间的元素总数为 n；合并每个区间只线性扫描，所以一层工作量为 O(n)。
3. 本页实现每层都合并并复制结果，总时间为 Θ(n log n)，最好、平均与最坏情况同阶（n≥2）。

临时数组占 O(n)，递归调用深度占 O(log n)，总辅助空间为 O(n)。这份实现不是原地排序。相等时先取左半部分，才能保留相等元素原有顺序。跳过已排序区间的其他实现可能有不同的最好情况，不能与这里混算。

半开区间实现与相等元素的顺序

例1：半开区间归并排序

#include <iostream>
#include <vector>
using namespace std;
void mergeSort(vector<int>& a, vector<int>& tmp, int l, int r) {
    if (r - l <= 1) return;
    int m = l + (r - l) / 2;
    mergeSort(a, tmp, l, m); mergeSort(a, tmp, m, r);
    int i = l, j = m, k = l;
    while (i < m && j < r) tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
    while (i < m) tmp[k++] = a[i++];
    while (j < r) tmp[k++] = a[j++];
    for (int p = l; p < r; ++p) a[p] = tmp[p];
}
int main() {
    vector<int> a = {3, 1, 2, 1}, tmp(a.size());
    mergeSort(a, tmp, 0, a.size());
    for (int x : a) cout << x << " ";
    cout << endl;
}

输出 1 1 2 3。临时数组防止覆盖尚未读取的原元素，某一侧用尽后必须复制另一侧余下部分。

例2：相等时如何保证稳定

左半部分是 (分数80,甲)，右半部分是 (分数80,乙)，甲原本排在乙前面。

关键字相等时先拿左边的甲，合并后次序不变。若总是先拿右边，相等元素可能倒序，稳定性就丢失了。

提示

• 所有递归和合并都使用同一种区间约定，闭区间与半开区间不能混写。
• 稳定性取决于实现细节，相等时选右边就不保证稳定。
• 空数组和单元素区间应立即返回，否则可能无限递归。

先修知识

• 冒泡、插入、选择排序及稳定性
• 递归

技术参考

• Stanford CS106B: sorting

范围说明

本站讲解由 InfoCode 编写，不是官方考纲；参考级别是本站映射，不代表官方等级、认证或参赛资格。练习记录不等于掌握或资格。

参考级别：GESP 5 级（本站映射）

查看赛事关系与路径