2.2 归并排序

将两个有序的数组归并成一个更大的有序数组。

归并排序吸引人的性质是它能够保证将任意长度为N的数组排序所需时间和NlogN成正比。

主要缺点是所需的额外空间和N成正比。

属于稳定排序方法:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的）。

一 原地归并的抽象方法

先将所有元素复制到辅助数组中，然后再归并回a[]中。

二 自顶向下的归并排序

应用高效算法设计中分治思想最典型的一个例子。这段递归代码是归纳证明算法能够正确地将数组排序的基础：如果它能将两个子数组排序，它就能够通过归并两个子数组将整个数组排序。

分治思想：基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。

自顶向下的归并排序需要1/2NlgN至NlgN次比较，最多访问数组6NlgN次。

改进

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

2.测试数组是否有序

3.不将元素复制到辅助数组

三 自底向上的归并排序

统计意义上来说,自顶向下的归并排序速度略微大于自底向上的归并排序

自底向上的归并排序比较适合用链表组织的数据。

当数组长度为2的幂时，它和自顶向上的归并排序所用的比较次数和数组访问次数正好相同，知识顺序不同。

四 排序算法的复杂度

用决策树可以证明