核心：有序子列的归并

递归算法

• 分而治之：假设有一段数据需要排序，那么我们将整个数据一分为二，先递归的将左边排好序，再递归的将右边排好序，然后得到左右都有序的子序列，最后调用上面的函数排序。

• 时间复杂度的分析：假设整个数据需要的时间为，则对于左右半边，其数据量为整个的一半，时间为，而 Merge 需要的时间为，可以得到如下递推公式：
最后可以得到：



 

• 注意到，归并排序的时间复杂度是确定的，恒等于；同时，归并排序也是稳定的排序。

• 对于排序算法，统一的接口是 ElementType A[], int N ，所以还需要为归并排序设计一个统一的接口。
❓
每次 Merge 实际上只用到了临时数组 TmpA 的一部分，为什么要一开始在 Merge_Sort 就申请临时数组，而不是在 Merge 中再申请呢？
实际上，虽然每次只用到了一部分，但是如果在 Merge 中申请数组，会导致每次 Merge 都 malloc 又 free ，操作繁琐，不如一开始就申请好。

非递归算法

• 这里的 Merge1 与原来的 Merge 的区别在于，最后不需要把 TmpA 中元素重新复制到 A 中；

• 如果归并数据的长度不是2的幂次方，最后会剩下一个“尾巴”，所以 Merge_pass 中 i <= N-2*length 的目的是在最后一个尾巴的地方停下，单独处理尾巴；

• 如果 i+length<N ，说明最后还剩下2个子列，那么再调用一次 Merge1 归并一次；否则直接将最后一段导入到 TmpA 中即可；

• 在 Merge_Sort 的 while 循环中，如果在 Merge_pass( A, TmpA, N, length ) 就已经全部归并完毕，那么在经过一次 Merge_pass( A, TmpA, N, length ) 就可以将 TmpA 中的数据导入到 A 中。

• Merge_Sort 是稳定的；

• 因为 Merge_Sort 需要额外的空间，并且需要在两个数组间来回复制元素，所以实际一般不用于做内排序，而是用于外排序。