归并排序
复习
- 冒泡排序与选择排序：两种
O(n²)的简单排序 - 插入排序：插入排序像整理扑克牌，把新牌插入已排好的部分
- 分治：分、治、合
TL;DR
- 归并排序用分治：先分别排好两半，再合并
- 合并两个有序序列，可以做到线性时间
- 它的时间稳定在
O(n log n) - 代价是需要额外的存储空间
正文
有了分治，就可以造出第一种高效的排序——归并排序（merge sort）。它把“排序”这个难题，巧妙地拆成了“合并两个有序序列”这个简单题。
先分到底，再逐层合并
归并排序的流程很规整：
- 分：把数组一分为二
- 治：递归地对两半分别排序，直到每段只剩一个元素（一个元素天然有序）
- 合：把两个已排好序的半边，合并成一个有序的整体
关键在于：排序的问题，被转化成了“合并”。
合并为什么是线性的
合并两个已经有序的序列，有个很简单的办法：用两个指针，分别指向两个序列的头部。
每次比较两个指针指向的元素，把较小的那个取出来放进结果，然后让对应指针后移。重复下去，直到某个序列取完，再把剩下的整个接上。
因为每个元素恰好被取出一次，所以合并的代价是 O(n)——线性的。这也是归并排序能高效的关键：它把“排序”换成了廉价的“合并”。
为什么是 O(n log n)
看看递归的“分层”：
- 每一层，整体都要做一轮合并，合起来是
O(n) - 数组每次对半分，从 n 分到 1，一共分出约
log n层
每层 O(n)，共 log n 层，合起来就是 O(n log n)。而且，无论数据原本是什么样子，这个代价都稳定成立——归并排序没有“最坏会退化”的问题。
代价：额外空间
归并排序也有短板：合并时需要一个额外的数组来暂存结果，所以它需要 O(n) 的额外空间。
这和快速排序形成了对比——快排可以就地排序、更省空间，但最坏情况下可能退化。O(n log n) 的时间，是用额外的空间换来的。
另外，归并排序还是稳定的（合并时先取左边相等的元素即可）。综合来看，它在稳定性和最坏表现上都很出色，代价就是那份额外的空间。
思考题 1
归并排序“合并”这一步，为什么能做到线性时间？
思考题 2
归并排序的时间复杂度为什么是
O(n log n)？
小结
知识点
- 归并排序用分治：分到单个元素，再逐层合并
- 合并两个有序序列是
O(n) - 总时间稳定为
O(n log n) - 需要
O(n)额外空间，且是稳定排序
参考资料
- Wikipedia(zh)：归并排序：基于分治与合并的排序算法
- Wikipedia(zh)：分治法：归并排序的理论基础
思考题答案（仅供参考）
思考题 1
因为两个序列都已经有序，可以用双指针：每次比较两个头部，取较小的放进结果并移动对应指针。每个元素只被取出一次，所以总代价与元素总数成正比，是线性的。
思考题 2
因为分治的每一层都要做一轮总体合并，合计 O(n)；而数组每次对半分，从 n 分到 1 共约 log n 层。每层 O(n)、共 log n 层，相乘即为 O(n log n)。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪