使用插入排序的合并排序的修改版本
Modified version of merge sort which uses insertion sort
我使用归并排序划分数组后，直到数组长度为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
测量一下。
最佳阈值取决于您的编程语言、数据类型、数据集值分布、计算机硬件、归并排序和插入排序的实现细节等。
通常这个值在10-200之间，最佳值增益不是很大
我觉得这对我的问题 http://atekihcan.github.io/CLRS/P02-01/ 来说是一个更合适的答案，在这里引用它，
为了使修改后的算法具有与标准归并排序相同的渐近 运行ning 时间，
Θ(nk+nlg(n/k))=Θ(nk+nlgn−nlgk)
必须与
相同
Θ(nlgn).
为了满足这个条件，k 不能渐进地比 lgn 增长得更快（如果 k 增长得比 lgn 快，因为有 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 相比非常小。
我使用归并排序划分数组后，直到数组长度为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
测量一下。
最佳阈值取决于您的编程语言、数据类型、数据集值分布、计算机硬件、归并排序和插入排序的实现细节等。
通常这个值在10-200之间，最佳值增益不是很大
我觉得这对我的问题 http://atekihcan.github.io/CLRS/P02-01/ 来说是一个更合适的答案，在这里引用它，
为了使修改后的算法具有与标准归并排序相同的渐近 运行ning 时间，
Θ(nk+nlg(n/k))=Θ(nk+nlgn−nlgk)
必须与
相同Θ(nlgn).
为了满足这个条件，k 不能渐进地比 lgn 增长得更快（如果 k 增长得比 lgn 快，因为有 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 相比非常小。