归并排序把数组一分为二，递归排序左右两半，再把两个有序子数组归并成一个有序数组。

Ph1zの理解： 归并排序是分治思想的"教科书范例"——大问题拆成小问题，小问题解决了，合并起来大问题也解决了。就像整理一摞试卷：先分成两半分别排好，再把两摞有序的试卷逐个比较，合并成一摞。

代码

void mergeSort(int a[], int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    mergeSort(a, l, mid);
    mergeSort(a, mid + 1, r);
    merge(a, l, mid, r);
}

正确性证明

归并排序的证明使用"分治法 + 归并保持有序"。

• 归并前提： 左右两半都已经有序（递归假设）。
• 归并过程： 每次取两段头部较小的元素放进辅助数组，直到一段耗尽；另一个剩余元素直接追加。
• 归并结果： 新数组中每次取出的元素都不小于已放入的元素，因此最终得到的数组有序。
• 递归基础： 单元素显然有序。

Ph1zの理解： 归并就像合并两个已经排好队的队伍——每次看两队排头谁更矮，谁先出列。因为两队本身有序，所以出队的人也一定是有序的。

因此整个数组最终有序。 ✓

复杂度分析

递推为：

$$T(n)=2T(n/2)+O(n).$$

拆解： $a=2$（分成 2 个子问题），$b=2$（每个规模减半），$f(n)=O(n)$（归并的代价）。$n^{{\log }_{2}2}=n$，$f(n)=\mathrm{\Theta }(n)$，属于主定理情况 2。

按主定理：

$$T(n)=\mathrm{\Theta }(n\log n).$$

而且最好、平均、最坏全是 $O(n\log n)$——归并排序不挑数据，稳定发挥。这是它最大的优点。

额外空间： 归并时需要辅助数组，$O(n)$。

稳定性： 稳定。因为归并时对相等元素优先取左侧段，保留原相对顺序。

归并排序 vs 快速排序： 归并排序最坏也是 $O(n\log n)$，而且稳定——那为什么实战中快排更常用？因为快排是原地排序（不需要 $O(n)$ 辅助数组），而且缓存友好（数据访问局部性好），常数因子更小。归并排序则在对稳定性有要求的场景（如外部排序、链表排序）中不可替代。