我所理解的归并排序算法
作者：goal00001111（高粱）
始发于goal00001111的专栏；允许自由转载，但必须注明作者和出处
引子：这篇文章以前写过，最近复习排序算法，觉得以前的代码还可以改进，因此有了此文。
归并排序算法以O（NlogN）最坏情形运行时间运行，而所使用的比较次数几乎是最优的。
该算法中最基本的操作是合并两个已排序的表，这只需要线性的时间，但同时需要分配一个临时数组来暂存数据。
归并排序算法可以用递归的形式实现，形式简洁易懂。如果N=1，则只有一个元素需要排序，我们可以什么都不做；否则，递归地将前半部分数据和后半部分数据各自归并排序，然后合并这两个部分。
归并排序算法也可以用非递归的形式实现，稍微难理解一点。它刚好是递归分治算法的逆向思维形式，在使用递归分治算法时，程序员只需考虑将一个大问题分成若干个形式相同的小问题，和解的边界条件，具体如何解决这些小问题是由计算机自动完成的；而非递归形式要求程序员从最基本的情况出发，即从解决小问题出发，一步步扩展到大问题。
我这里两种形式都给出。
另外，很多人在写递归形式的归并排序算法时，临时数组是在MergeSort函数中分配的，这使得在任一时刻都可能有logN个临时数组处在活动期，如果数据较多，则开销很大，实用性很差。
我把临时数组设置在Merge函数中，避免了这个问题。
///////////////////////////////////////////////////////////////////////
递归形式：
template <class
T>
void MSort(T a[], int
left, int right)
{
if (left < right)
{
int center = (left + right) / 2;
MSort(a, left, center);
MSort(a, center+1, right);
Merge(a, left, center+1, right+1);
}
}
template <class
T>
void MergeSort(T a[],
int n)
{
MSort(a, 0, n-1);
}
///////////////////////////////////////////////////////////////////////
非递归形式：
算法介绍：先介绍三个变量beforeLen，afterLen和i的作用：
int beforeLen; //合并前序列的长度
int afterLen;//合并后序列的长度，合并后序列的长度是合并前的两倍
int i = 0;//开始合并时第一个序列的起始位置下标，每次都是从0开始
i，i+beforeLen，i+afterLen定义被合并的两个序列的边界。
算法的工作过程如下：
开始时，beforeLen被置为1，i被置为0。外部for循环的循环体每执行一次，都使beforeLen和afterLen加倍。内部的while循环执行序列的合并工作，它的循环体每执行一次，i都向前移动afterLen个位置。当n不是afterLen的倍数时，如果被合并序列的起始位置i，加上合并后序列的长度afterLen，超过输入数组的边界n，就结束内部循环；此时如果被合并序列的起始位置i，加上合并前序列的长度beforeLen，小于输入数组的边界n，还需要执行一次合并工作，把最后长度不足afterLen，但超过beforeLen的序列合并起来。这个工作由语句Merge(a, i, i+beforeLen, n);完成。
template <class
T>
void MergeSort(T a[],
int n)
{
int beforeLen; //合并前序列的长度
int afterLen = 1;//合并后序列的长度
for (beforeLen=1; afterLen<n; beforeLen=afterLen)
{
afterLen = beforeLen << 1; //合并后序列的长度是合并前的两倍
int i = 0;//开始合并时第一个序列的起始位置下标，每次都是从0开始
for ( ; i+afterLen<n; i+=afterLen)
Merge(a, i, i+beforeLen, i+afterLen);
if (i+beforeLen < n)
Merge(a, i, i+beforeLen, n);
}
}
///////////////////////////////////////////////////////////
上面两种算法都要用到下面的合并函数。
/*函数介绍：合并两个有序的子数组
输入：数组a[]，下标left，center，元素个数len，a[left]~a[center-1]及a[center]~a[len-1]已经按非递减顺序排序。
输出：按非递减顺序排序的子数组a[left]~a[len-1]。
*/
template <class
T>
void Merge(T a[], int
left, int center, int len)
{
T *t = new T[len-left];//存放被合并后的元素
int i = left;
int j = center;
int k = 0;
while (i<center && j<len)
{
if (a[i] <= a[j])
t[k++] = a[i++];
else
t[k++] = a[j++];
}
while (i < center)
t[k++] = a[i++];
while (j < len)
t[k++] = a[j++];
//把t[]的元素复制回a[]
for (i=left,k=0; i<len; i++,k++)
a[i] = t[k];
delete []t;
}