尽管合并排序最坏情况运行时间为O(nlgn)，插入排序的最坏运行时间为O(n^2)，但是插入排序的常数因子使得它在n较小时，运行要更快一些。因此，在合并排序算法中，当子问题足够小时，采用插入排序就比较合适了。考虑对合并排序做这样的修改，即采用插入排序策略，对n/k 个长度为 k 的子列表进行排序。然后，再用标准的合并机制将它们合并起来，此处k是一个待定的值。但
阅读背景：
归并排序中对小数组采用插入排序
来源：互联网
分享到：
