使用插入排序的合并排序的修改版本

Question

我使用合并排序分割数组后，直到数组长度为k，我应该在k长度数组上使用插入排序，然后继续合并。什么应该是k的最优值？

另外，我发现与我的类似这些问题，但没有找到一个明确的答案 Choosing minimum length k of array for merge sort where use of insertion sort to sort the subarrays is more optimal than standard merge sort Modification to merge sort to implement merge sort with insertion sort Java

Answer 1

这个我觉得是我的问题http://atekihcan.github.io/CLRS/P02-01/一个更加合适的回答，在这里引用它，

对于改进算法具有相同的渐近运行时间作为标准归并排序，

Θ(nk+nlg(n/k))=Θ(nk+nlgn−nlgk) 

必须同

Θ(nlgn). 

为了满足这个条件，K不能长得比渐近lg⁡n更快（如果k增长，因为NK任期比lg⁡n快，该算法将运行在比θ（nlgn）更差的渐近时间处。但只是这个论点是不够的，因为我们必须检查

k=Θ(lgn), 

该要求是否成立。

如果我们假定，

k=Θ(lgn), 

Θ(nk+nlg(n/k))=Θ(nk+nlgn−nlgk)=Θ(nlgn+nlgn−nlg(lgn))=Θ(2nlgn−nlg(lgn))†=Θ(nlgn) 

†LG（LGN）相比LGN为充分大的n值是非常小的。

Answer 2

只是衡量。

最佳阈值取决于您的编程语言，数据类型，daata设置值分布，计算机硬件，合并排序和插入排序实现细节等。

通常这个值在10-200范围内，最佳值的增益不是很重要。