形式陈述

归并排序把长度 $n$$n$ 的序列分成两个近半子序列，递归排序后在线性时间内合并两个有序结果。其比较时间满足

$$ T(n)=T(\lfloor n/2\rfloor)+T(\lceil n/2\rceil)+\Theta(n)=\Theta(n\log n). $$$$T(n)=T(\lfloor n/2\rfloor )+T(\lceil n/2\rceil )+\mathrm{\Theta }(n)=\mathrm{\Theta }(n\log n).$$

标准数组实现需要 $\Theta(n)$$\mathrm{\Theta }(n)$ 辅助空间；链表实现可通过指针重连降低额外元素存储。合并时若相等键优先取左半部分，则算法稳定。最坏比较数与输入排列无关地保持 $O(n\log n)$$O(n\log n)$。

直觉

把难以整体排序的问题拆成两个有序列表后，合并只需比较各自尚未取出的最小元素，因此每个元素每层只被处理常数次。

例子与边界

排序 [4,1,3,2]，先得 [1,4] 与 [2,3]，再线性合并为 [1,2,3,4]。自然归并排序可利用输入中已有的有序段。归并排序不必原地；声称标准数组版本只需 $O(1)$$O(1)$ 额外空间是错误的，虽然存在更复杂的原地归并算法。它的 $\Theta(n\log n)$$\mathrm{\Theta }(n\log n)$ 比较数达到一般比较排序下界的渐近最优阶。

推论与应用

归并排序适合链表、外部存储和稳定排序，也构成外部多路归并与并行排序的基础。它还是分治递推分析的标准例子。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Ch. 2, merge sort and recurrence analysis。
• Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998，Vol. 3, §5.2.4, sorting by merging。