（在归并排序中对小数组采用插入排序）虽然归并排序的最坏情况运行时间为)
，而插入排序的最坏情况时间为)
，但是插入排序中的常量因子可能使得它在n较小时，在许多机器上实际运行的更快。因此，在归并排序中当子问题变得足够小时，采用插入排序来使递归的页变粗是有意义的。考虑对归并排序的一中修改，其中使用插入排序来排序长度为k的n/k个子表，然后使用标准的合并机制来合并这些子表。这里k是一个待定的值：
a.证明：插入排序最坏情况可以在)
时间内排序每个长度为k的n/k个子表。
b.表明在最坏情况下如何在))
时间内合并这些子表。
c.假定修改后的算法的最坏情况运行时间为))
时间内合并这些子表。
d.在实践中，我们应该如何选择k?
