归并排序

概述

归并排序（Merge Sort）是一种基于分治法的排序算法。其核心过程为：将数组分解为两半，递归排序两半，然后合并两个有序子数组。归并排序在所有情况下（最好、最坏、平均）的时间复杂度均为 $\Theta (n\log n)$，且是稳定排序。其缺点是需要 $\Theta (n)$ 的额外空间。

定义

归并排序（Merge Sort）

归并排序遵循分治法的三步：

1. 分解（Divide）：将数组 $A[p..r]$ 分为两个子数组 $A[p..q]$ 和 $A[q+\mathrm{1..}r]$，其中 $q=\lfloor (p+r)/2\rfloor$
2. 解决（Conquer）：递归地对两个子数组进行归并排序
3. 合并（Merge）：将两个已排序的子数组合并为一个有序数组

合并操作在 $\Theta (n)$ 时间内完成：使用两个指针分别扫描两个子数组，每次取较小的元素放入结果数组。

核心性质

性质	描述	备注
时间复杂度	$\Theta (n\log n)$（所有情况）	由递推 $T(n)=2T(n/2)+\Theta (n)$ 决定
空间复杂度	$\Theta (n)$	需要辅助数组进行合并
稳定性	稳定排序（相等元素的相对顺序不变）	适合多关键字排序
非原地排序	需要额外空间	区别于快速排序
适合外部排序	顺序访问模式适合磁盘/磁带	大数据排序的首选

复杂度分析

递推关系：$T(n)=2T(n/2)+\Theta (n)$

由主定理：$a=2,b=2,f(n)=\Theta (n)=\Theta (n^{{\log }_{2}2})$，适用情形二：

$T(n)=\Theta (n\log n)$

归并排序 vs 快速排序

比较维度	归并排序	快速排序
时间复杂度	$\Theta (n\log n)$（所有情况）	期望 $\Theta (n\log n)$，最坏 $\Theta (n^2)$
空间复杂度	$\Theta (n)$	$\Theta (\log n)$（递归栈）
稳定性	稳定	不稳定
原地排序	否	是
缓存性能	较差（顺序访问辅助数组）	较好（原地操作）
实际速度	通常稍慢	通常更快

应用场景

• 外部排序：处理无法全部装入内存的大规模数据
• 稳定排序需求：需要保持相等元素原始顺序的场景
• 链表排序：归并排序非常适合链表，不需要额外空间
• 多路归并：归并思想扩展到 $k$ 路归并，用于外部排序和数据库

参见

• 分治法 — 归并排序的设计策略
• 快速排序 — 另一种分治排序算法
• 主定理 — 分析归并排序复杂度的工具
• 递归关系式 — 归并排序的递推关系
• 递归树 — 归并排序递推关系的可视化分析
• 动态多线程 — 并行归并排序