如何选择子块大小进行合并sort+insertion排序

Question

这里有一个小分歧的问题，由于我找不到我想要问的问题，所以我的问题如下：

在Cormen的“算法简介”第2节，问题2.1中，选项d要求，如果一个人想要将合并排序和插入排序结合起来，以减少时间，因为插入排序在小规模的输入上可以因为系数较小而更快，方法是将n的输入大小划分为k个片段，然后在这个n/k小块上进行插入，如何选择k？

我的尝试是，考虑组合排序的最坏情况和正常合并排序的最佳情况，然后找一个合适的k作为下界，因为在最坏的情况下，我认为n/k分段将需要k^2/2时间(可能有附加的项，但仅考虑前导系数)，因此总共需要nk/2步骤。另外，使用合并排序将需要nlg(n/k)时间，因此考虑到以下几点：nk/2+nlg(n/k)=nlg(n)给出了k=2,4，但我也看到人们说k=10或15没有问题，那么如何改进呢？

备注：

很抱歉缺乏乳胶的风格，这是我第一次在这个网站上，所以我将寻找一个编辑和建议。

Answer 1

不幸的是，答案在很大程度上取决于插入排序部分和合并排序部分的实际实现，以及它们的成本与比较成本的比较。

例如，如果比较非常昂贵，那么合并排序在任何大小> 3的情况下都会更好。

渐近表示法的全部要点是独立于实际的操作成本，因此使用渐近界来评估特定大小的合并排序与特定大小的插入排序的成本。你需要真正的数字。

实际的决定方法是通过对各种实际用例的实验。我听说从快速排序切换到插入排序的最佳点通常是7项左右。我还没听说过类似的故事。