【8.5】归并排序

归并排序思想:

• 划分为两个子序列
• 分别对每个子序列归并排序
• 有序子序列合并

两路归并排序：

归并函数：

归并算法优化：

• 同优化的快速排序一样，对基本已排序序 列直接插入排序
• R.Sedgewick 优化:归并时从两端开始 处理，向中间推进，简化边界判断

R.Sedgewick优化归并思想：

优化的归并排序(阈值28)：

优化的归并函数：

算法复杂度分析

• 空间代价:Θ(n)
• 划分时间、排序时间、归并时间
• T(n) = 2T (n / 2) + cn
• T(1) = 1
• 归并排序总时间代价也为
• Θ(nlog n)
• 不依赖于原始数组的输入情况，最大、最小以及平均时间代价均为 Θ(nlog n)

思考

• 普通归并和 Sedgewick 算法都是稳定的吗?
• 两个归并算法哪个更优?
• 二者的比较次数和赋值次数
• 归并时子序列下标是否需要边界判断

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾