归并排序动画

算法原理

归并排序（Merge Sort）是分治法的教科书样本：把「给 8 个数排序」这个大问题，层层对半劈成「给 1 个数排序」的平凡问题，再把排好序的小段两两归并成更大的有序段，直到合成完整答案。它的时间复杂度稳定在 O(n log n)，且是稳定排序的代表实现。

动画把这个过程拆成两个阶段：

1. 分（Splitting）：8 个数字包在一块光晕里，第 1 层从中间劈 1 刀，第 2 层同时劈 2 刀，第 3 层同时劈 4 刀——每层刀数翻倍，直到 8 个格子各自成段；劈完全部格子整体上移一行，给合并腾出舞台；
2. 合（Merging）：两段按归并取数顺序（比较两段队首，小者先飞入）逐格落到下方，间距为 0 紧贴成新的有序段；每一层合并完成后整行集体上移，最终 8 格合成完整有序条（n=8 共 7 次归并）。

动画怎么看

• 金色光晕：当前段的范围。分阶段它从 1 块逐层分裂成 8 块，合阶段它框住正在归并的两段；
• 格子飞入：合并时按「小左大右」逐格落位，每拍飞入一格；
• 集体上移：每层归并完成，该行整体上移一层，体现「层数 = log₂n」。

动画下方有一行实时解说（如 分治·分·第 2 层：同时劈开 2 段（a[0..1)、a[1..3)…、合并 a[0..1) 与 a[1..2)），可以数一数：劈分层数正好是 ⌈log₂8⌉ = 3 层，每层归并的总比较量是 O(n)——O(n log n) 的由来一目了然。

复杂度分析

C++ 参考代码

#include <iostream>
#include <vector>
using namespace std;

// 合并两个各自有序的区间 a[l..m) 与 a[m..r)
void merge(vector<int>& a, int l, int m, int r, vector<int>& tmp) {
    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];
}

// 递归对半劈分，再逐层归并
void mergeSort(vector<int>& a, int l, int r, vector<int>& tmp) {
    if (r - l <= 1) return;                // 单个元素天然有序
    int m = l + (r - l) / 2;               // 从中间劈开
    mergeSort(a, l, m, tmp);
    mergeSort(a, m, r, tmp);
    merge(a, l, m, r, tmp);
}

int main() {
    vector<int> a = {38, 17, 52, 9, 41, 25, 60, 13};
    vector<int> tmp(a.size());
    mergeSort(a, 0, a.size(), tmp);
    for (int x : a) cout << x << ' ';      // 输出：9 13 17 25 38 41 52 60
    cout << endl;
    return 0;
}

什么时候用归并排序

归并排序最坏情况也只有 O(n log n) 且稳定，这是快排都不具备的组合，因此 std::stable_sort、数据库外部排序、对链表排序都用它。代价是 O(n) 辅助空间。CSP 阶段它有两层意义：一是「分治 + 合并」思想的模板（逆序对统计正是借助归并过程），二是外部排序、多路归并等工程题目的理论基础。