???? 合并排序的runningtime是O(nlgn),插入排序?yàn)镺(n*n),當(dāng)合并排序的劃分到一定程度時(shí)可以應(yīng)用插入排序。此時(shí)插入排序比合并排序的效率高,所以對(duì)合并排序做個(gè)修改：n/k 長(zhǎng)度為k的子序列用插入法排序。（要確定k的值）
a.證明最壞情況下，n/k個(gè)子序列用插入來(lái)排序的時(shí)間時(shí)O(nk).
???插入排序?yàn)镺(n*n)，那么對(duì)長(zhǎng)度為k的子序列排序?yàn)镺(k*k),n/k個(gè)子序列排序時(shí)間和是(n/k)*O(k*k)=O(n*k),得證
b.證明在最壞情況下各子序列可以在O(nlg(n/k))下合并.
c.設(shè)修改后合并算法的時(shí)間階為O(nk+nlg(n/k)).請(qǐng)給出最大漸近值k（以O(shè)記號(hào)，k是n的函數(shù)）使得修改后的算法有和標(biāo)準(zhǔn)合并算法一樣的漸近運(yùn)行時(shí)間
d.k的值在實(shí)際中如何確定？