归并排序中对小数组采用插入排序 | 飞污熊博客

[yidao620c]

https://www.xncoding.com/algorithm/merge-sort.html

纯归并排序的复杂度为O(nlgn)，而纯插入排序的时间复杂度为O(n^2)。数据量很大的时候采用归并排序。 但是在n较小的时候插入排序可能运行的会更快点。因此在归并排序中当子问题变得足够小时， 采用插入排序来使得递归的叶子变粗可以加快排序速度。那么这个足够小到底怎么去衡量呢？ 请看下面： 这么几个我不证明了，比较简单： 插入排序最坏情况下可以在O(nk)时间内排序每个长度为k的n/k个