总体思想

假设初始序列含有n个元素，则可以看成n个有序的子序列，每个子序列只有一个元素，然后两两归并，得到（n/2+0.5）个长度为2或者1的有序子序列，再两两归并……如此反复执行，直到得到一个长度为n的有序序列为止，这种排序方法称之为2路归并排序。

技巧

再按照两两归并的步骤往上归并，子序列又从n个变为（n/2+0.5）个，在原来的数量上缩减为原来的一半，但每一个子序列都变成了有序的，且有序子序列的长度逐步翻倍，最终只有一个子序列，就是排好序的序列。

有点像“先向下开花，再向上收拢”的感觉

#include 
using namespace std;

#define MAXSIZE 100
typedef int Status;

#define OK  1
#define ERROR 0
#define TRUE  1
#define FALSE 0

template 
class SqList
{
public:
    T r[MAXSIZE+1];
    int length;
public:
    SqList(T * var,int len);
    SqList();
    void printList();

    Status swapElement(int i, int j);


    void MergeSort();
    void MSort(T src[],T dst[],int s,int t);
    void Merge(T src[],T dst[],int i,int m,int n);
    void MergeSort_2();

};

template 
SqList::SqList(T * var,int len)
{
    length = len/sizeof(T);
    memcpy(&(r[1]), var, len);
}

template 
SqList::SqList()
{
    memset(this, 0, sizeof(SqList));
}

template 
Status SqList::swapElement(int i,int j)
{
    T tmp =this->r[i];
    this->r[i] = this->r[j];
    this->r[j] = tmp;
    return OK;
}

template 
void SqList::printList()
{
    for (int i = 1; i <= length; i++)
    {
        cout << this->r[i] << "\t";
    }
    cout << endl;
}

/************************************************************************/
/*归并排序                                                                      */
/************************************************************************/

/*为了统一接口--内部调用实际的归并排序函数*/
template 
void SqList::MergeSort()
{
    MSort(r, r, 1, length);//调用实际的归并排序
}


/*归并排序的递归算法
将src[s..t]归并排序为dst[s..t]*/
template 
void SqList::MSort(T src[], T dst[], int s, int t)
{
    int m = 0;
    T tmp[MAXSIZE+1];//开头是一个哨兵--辅助变量存放各阶段归并的结果
    memset(tmp, 0, sizeof(tmp));

    if (s == t)//递归结束的条件--意味着两两归并的子序列中都只有一个元素
    {
        dst[s] = src[s];//由于只有一个元素--直接存放元素到目标表
                        //表示两个有序子序列，只不过每个子序列只有一个元素
                        //执行完这条语句表示递归结束，该返回了
                        //紧接着执行Merge函数完成对这两个子序列的归并操作
    }
    else{
        m = (s + t) / 2;//将src[s..t]评分为src[s..m]和src[m+1..t]

        MSort(src, tmp, s, m);//递归将src[s..m]归并为tmp[s..m]
        MSort(src, tmp, m + 1, t);//递归将src[m+1..t]归并为tmp[m+1..t]

        Merge(tmp, dst, s, m, t);//将tmp[s..m]和tmp[m+1..t]归并到dst[s..t]
                                //每次递归返回的时候都会执行这条语句，
                                //里面完成了两个局部有序子序列的归并操作
                                //这条语句执行完以后就会得到局部的有序序列以供外层递归返回时
    }

}


/*将有序的src[i..m]和src[m+1..n]归并为dst[i..n]
默认序号小的子序列比序号大的子序列要小--升序排列
*/
template 
void SqList::Merge(T src[], T dst[], int i, int m, int n)
{
    int j, k, l;//j是目标序列的下标，从i到n
                //k是第二个有序子序列的下标，从m+1开始到n
                //第一个有序子序列的下标就用i来表示，从i到m
                //l是用来处理有序子序列剩下的元素的辅助变量
                //因为最后可能子序列的个别元素会在循环结束后还没有存放到目标表/序列中
    for (j = i, k = m + 1; i <= m && k <= n;j++)
    {
        if (src[i] < src[k])
            dst[j] = src[i++];
        else
            dst[j] = src[k++];
    }

    if (i <= m)//将剩余的src[i..m]复制到dst中
    {
        for (l = 0; l <= m - i;l++)//这里循环m-i+1次，因为剩下的元素下标从i开始，
                                    //直到m结束，一共就是m-i+1个
        {
            dst[j + l] = src[i + l];
        }
    }

    if (k <= n)//将剩余的src[k..n]复制到dst中
    {
        for (l = 0; l <= n - k; l++)//这里循环n-k+1次，因为剩下的元素下标从k开始，
                                //直到n结束，一共就是m-i+1个
        {
            dst[j + l] = src[k + l];
        }
    }
}

template 
void SqList::MergeSort_2()
{

}
int main(void)
{
    int myList[9] = {90,10,50,80,30,70,40,60,20};
    SqList list(myList,sizeof(myList));

    cout << "before sort:"<< endl;
    list.printList();

    list.MergeSort();
    cout << "after sort:" << endl;
    list.printList();

    cout<<"Hello!"<

复杂度

堆排序和现在介绍的归并排序的时间复杂度都是O( nlogn )，而对于递归思想的归并排序空间复杂度是O( n+logn )，比较耗费内存，但不管如何他稳定（没有跳跃式的比较和交换），高效，时间复杂度不到O( n2 )。

非递归的归并排序