归并排序Merge sort
将有序子序列逐层归并，逐步形成整体有序序列。
- 核心约束
- 归并的输入子序列已有序，输出保持整体有序。
- 适用问题
- 稳定排序与外部排序。
- 边界与取舍
- 实际项目仅归并已有序输入时，应单独归类为有序归并。
时间与空间#
n 为元素数；比较和移动一个元素按 计算。
- 时间复杂度
- 经典实现最好 / 平均 / 最坏
- 辅助空间
- 数组归并 ，另有 递归栈
先分割再归并；相等元素优先取左侧可保持稳定。链表原地重连、自然归并及提前跳过有序段的实现有不同辅助空间或最好情况。
工程中的应用#
2 个案例 · 附源码Linux DRM 使用通用 list_sort 对显示模式链表排序；底层归并通过相等时优先取较早元素来保持稳定性。
附源码片段 · 索引与查找
CPython 的列表排序识别已有序段，补齐短段，再按 Powersort 策略稳定归并，兼顾局部有序输入与通用排序。
附源码片段 · 检索与计算
基础原理参考资料
Princeton · Merge标准稳定归并排序的时间和额外内存。