在TimRun 文档的“计算 minrun”部分,它给出了为 N=2112 数组选择 minrun 的一个好例子和一个坏例子。它指出使用 minrun = 32 效率低下,因为
长度为 2048 和 64 的运行最终合并 自适应噱头可以通过少于 2048+64 次比较来做到这一点,但它仍然比必要的比较多,并且 - 合并排序相对于样本排序的错误 - 更多的数据移动(O (N) 复制只是为了让 64 个元素到位)。
它还将 minrun = 32 算法描述为:
然后我们有一个类似于“2112”的案例,再次为最后一次合并留下了太少的工作要做
然后它表示选择 minrun = 33 将得到一个更好的完美平衡合并。
如果我们在这种情况下采用 minrun=33,那么我们很可能最终得到 64 次运行,每个运行长度为 33,然后所有合并都是完美平衡的。更好的!
我的问题是,如果总元素数相同(示例中为 2112),为什么合并完美平衡的排序数组比不平衡数组更好?
当 minrun=33 的总元素也是 2112 时,为什么 minrun=32 “做的比较比必要的多”?
为什么会有“更多的数据移动”?
为什么最后一次合并“工作太少”?
我的理解是,合并大小为 A 和大小 B 的排序数组需要 O(A+B)。为什么 A 和 B 大小相同时效率更高?
我绘制了如何执行 2 个 minrun 场景的图表,但我仍然感到困惑。