在归并排序（合并排序）中的小数组使用插入排序

长度为n，分为n/k个小数组，每个长度为k

问K取何值时能使效率最高

易得O(n)=nk+nlg(n/k)

nk是n/k个小数组进行插入排序k×k，得nk

nlg(n/k)是n/k个数组进行归并需要lg(n/k)次合并，每次代价为n的的

答案

应为lgn

O(n)=nk+nlgn-nlgk

若k>lgn,则前半部分大于归并排序时间复杂度，，故K最大为lgn。

取最大值时应为最优