归并排序

概述

归并排序 是分治法策略的经典应用，通过递归地将数组分成两半分别排序，再将两个有序子数组合并，实现了 $\Theta (n\lg n)$ 的时间复杂度，是排序问题的高效解决方案之一。

定义

归并排序

归并排序遵循分治三步范式：

1. 分解：将含 $n$ 个元素的数组分成各含 $\lfloor n/2\rfloor$ 和 $\lceil n/2\rceil$ 个元素的两个子数组。
2. 解决：递归地对两个子数组分别调用归并排序。
3. 合并：调用 MERGE 过程，在 $\Theta (n)$ 时间内将两个已排序子数组合并为一个有序数组。

核心性质

• 时间复杂度：$\Theta (n\lg n)$，在所有情况下（最好、最坏、平均）均保持此复杂度。
• 空间复杂度：$\Theta (n)$，MERGE 过程需要辅助数组。
• 稳定性：归并排序是稳定排序。
• MERGE 过程：使用双指针法，在 $\Theta (n)$ 时间内完成两个有序子数组的合并，通过哨兵值（sentinel）简化边界处理。

章节扩展

第2章：入门

• 2.3 分治法：归并排序作为分治法的第一个完整示例，其递归关系式为 $T(n)=2T(n/2)+\Theta (n)$，解为 $T(n)=\Theta (n\lg n)$。

第1章：算法在计算中的角色

• 1.2 算法作为一种技术：对比插入排序的 $\Theta (n^2)$ 与归并排序的 $\Theta (n\lg n)$，说明高效算法对大规模数据处理的实际意义。

参见

• 分治法
• 插入排序
• 排序问题
• 递归关系式