归并排序详解

之前看了选择和插入排序，这两个算法是的时间复杂度均为O(n^2),而随着问题规模n的增大，插入和选择排序都比较慢。

归并排序时的时间复杂度为O（nlgn) 其主要思想是分治法(divide and conquer)，分就是要将n个元素的序列划分为两个序列，再将两个序列划分为4个序列，

直到每个序列只有一个元素，最后，再将两个有序序列归并成一个有序的序列。

例如两个序列：

要归并成一个有序的序列，按照我们常规的方法，我们每次从两个列表开头元素选取较小的一个，直到某一个列表到达底部，再将另一个剩下部分顺序取出。其实如果将每个元素最后添加一个最大值，则无需判断是否达到列表尽头。

代码如下：merge函数的功能为将A中[low,mid],[mid+1,high]归并成一个有序的片段。

template<class T> void merge(T A[],int low,int mid,int high)
{
    //low to mid as the left array   mid+1 to high as the right array
    int llen = mid-low+2;
    int rlen = high-mid+1;
    T *left = (T*)new T[llen];
    T *right = (T*)new T[rlen];
    //copy the low to mid to the temp array left
    for (int i=0;i<llen-1;i++)
    {
        left[i] = A[low+i];
    }
    for (i=0;i<rlen-1;i++)
    {
        right[i] = A[mid+1+i];
    }
    //set the sentinel
    left[llen-1] = numeric_limits<T>::max();
    right[rlen-1]= numeric_limits<T>::max();
    //merge the two array and copy to A[low,high];
    int j = 0;
    int k = 0;
    for (i = low; i < high+1 ;i++)
    {
        if (left[j] < right[k])
        {
            A[i] = left[j];
            j++;
        }
        else
        {
            A[i] = right[k];
            k++;
        }
    }   delete [] left;   delete [] right;
}

归并排序就是多次调用merge

template<class T> merge_sort(T A[],int low,int high)
{
    int mid = (low+high)/2;
    if (low < high)
    {
        merge_sort(A,low,mid);
        merge_sort(A,mid+1,high);
        merge(A,low,mid,high);
    }
}

这是一个递归算法，这个算法的理解其实可以借助下面这个图：

对于原始的数组2,1,3,8,5,7,6,4,10，在整个过程执行的是顺序是途中红色编号1-20。虽然我们描述中说的是程序先分解，再归并，但实际过程是一边分解一边归并，前半部分分先排好序，后半部分再拍好，最后整个归并为一个完整的序列，途中的merge过程它所在层的两个序列的merge过程：下图展示了每个merge过程对作用于数组的哪部分（红色）。

整个过程就像一个动态的树，执行顺序就是对树的先序遍历顺序。

最后实验验证，对10000个倒序的数组进行排序，直接插入排序需1024ms，二归并排序只需20ms。