摘要: 引子：这篇文章以前写过，最近复习排序算法，觉得以前的代码还可以改进，因此有了此文。
归并排序算法以O（NlogN）最坏情形运行时间运行，而所使用的比较次数几乎是最优的。
该算法中最基本的操作是合并两个已排序的表，这只需要线性的时间，但同时需要分配一个临时数组来暂存数据。
归并排序算法可以用递归的形式实现，形式简洁易懂。如果N=1，则只有一个元素需要排序，我们可以什么都不做；否则，递归地将前半部分数据和后半部分数据各自归并排序，然后合并这两个部分。
归并排序算法也可以用非递归的形式实现，稍微难理解一点。它刚好是递归分治算法的逆向思维形式，在使用递归分治算法时，程序员只需考虑将一个大问题分成若干个形式相同的小问题，和解的边界条件，具体如何解决这些小问题是由计算机自动完成的；而非递归形式要求程序员从最基本的情况出发，即从解决小问题出发，一步步扩展到大问题。
我这里两种形式都给出。
另外，很多人在写递归形式的归并排序算法时，临时数组是在MergeSort函数中分配的，这使得在
阅读全文