归并与插入混合排序

实验目的

分析插入排序作为归并排序递归终止条件时的成本与适用阈值。

实现要点

1. 对 n/k 个长度为 k 的子表进行插入排序，最坏总成本为 Θ(nk)。
2. 分层归并共需 Θ(n log(n/k)) 时间；保持 Θ(n log n) 的最大阈值数量级为 Θ(log n)。
3. 实际最优 k 与语言、硬件和输入有关，实验比较 k = 1、4、8、16、32、64、128。

报告与附件