8.5.1 归并排序
原书定位
印刷页P370起,对应PDF第382页。下文为目视整理的知识提要;完整内容见原书对照。
二路归并把两个有序段合为一个有序段,每次取两段首部较小者,某段用完后追加另一段。相等时先取左段记录可保持稳定。
自底向上每趟有序段长度约翻倍,共 趟;也可递归分半后归并。总时间 ,常规数组辅助空间 ,递归另有 栈。链表归并可重接指针,空间分析需按具体实现。
合并长度 的有序数组,直接双指针最多比较 次、最少 次;记录复制总量仍为 。比较次数的具体值随交错情况变化。

二路归并排序各趟结果,原书P370。
对应练习
关联知识
原书对照
展开原书对照截图

