在我使用合并排序划分数组后,直到数组的长度为k,我应该对k长度的数组使用插入排序,然后继续合并。k的最佳值应该是多少?
此外,我发现这些问题与我的相似,但没有找到确切的答案为合并排序选择数组的最小长度k,其中使用插入排序对子数组进行排序比标准合并排序更优化修改合并排序以使用插入排序实现合并排序Java
只需测量即可。
最佳阈值取决于您的编程语言、数据类型、数据集值分布、计算机硬件、合并排序和插入排序实现细节等
通常,该值在10-200的范围内,并且最佳值的增益不是很显著。
我觉得这是我问题的一个更恰当的答案http://atekihcan.github.io/CLRS/P02-01/,在这里引用,
为了使修改后的算法具有与标准合并排序相同的渐近运行时间,
Θ(nk+nlg(n/k))=Θ(nk+nlgn−nlgk)
必须与相同
Θ(nlgn).
为了满足这个条件,k不能比lg增长得更快n渐近地(如果k增长得比lg快n、 由于nk项的存在,该算法将在比θ(nlgn)更差的渐近时间下运行。但仅仅这个论点是不够的,因为我们必须检查
k=Θ(lgn),
该要求是否成立。
如果我们假设
k=Θ(lgn),
Θ(nk+nlg(n/k))=Θ(nk+nlgn−nlgk)=Θ(nlgn+nlgn−nlg(lgn))=Θ(2nlgn−nlg(lgn))†=Θ(nlgn)
†对于足够大的n值,lg(lgn)与lgn相比非常小。