归并排序最吸引人的性质是它能保证将任意长度为 N 的数组排序所需时间和 NlogN 成正比；它的主要缺点是它需要的额外空间与 N 成正比。

原地归并

自顶向下的归并排序

命题 F 和 G 告诉我们归并排序所需时间和 NlgN 成正比。这使得它非常适合对庞大数组进行排序。

对小规模子数组使用插入排序

插入排序非常适合处理小规模问题，所以再归并时通过插入排序处理小规模子数组，可以将整体排序时间缩短 10%~15%。

自底向上的归并排序

相较自顶向下，这个代码简单一些。

排序算法的复杂度

通过计算复杂度理解问题自身固有的难易程度，进而找到准确的上下界，让我们既有优化算法的动力，又不至于为不可能的性能改进投入资源。

下面就是证明排序算法的复杂度：

答疑