排序算法之归并排序

分治法：

    将原问题分解为几个规模较小但类似于原问题的子问题，递归得求解这些子问题，然后再合并这些子问题的解

来建立原问题的解。即遵循3个步骤：

    分解：将原问题分解为规模较小的若干实例。

    解决：递归求解各个子问题。然而，若子问题的规模足够小，则直接求解。

    合并：将子问题的解合并成原问题的解。

归并排序描述：

    归并排序完全遵从分治模式。直观上其操作如下：

    分解：分解待排序的n个元素的序列成各具n/2个元素的两个子序列。

    解决：使用归并排序递归地排序两个子序列。

    合并：合并两个已排序的子序列产生答案。

    当待排序的序列长度为1时，递归开始回升，在这种情况下不要做任何工作。

    以一个大小为8的数组为例进行归并排序，其过程如下：

           如橙色箭头所示，勾画出程序执行时递归栈(从左向右)的情况，当一个结点的左右子问题都执行结束时，调用merge函数。

算法实现：

int extra[N]; // 需要额外的空间
void merge(int low, int mid, int high)
{
    for(int i = low; i <= high; i++)
    {
        extra[i] = data[i];
    }
    
    int i = low, j = mid + 1, k = low;
    
    while(i <= mid && j <= high)
    {
        if(extra[i] <= extra[j]) 
        {
            data[k++] = extra[i++];
        }
        else 
        {
            data[k++] = extra[j++];
        }
    }
    
    while(i <= mid) 
    {
        data[k++] = extra[i++];
    }
    while(j <= high) 
    {
        data[k++] = extra[j++];
    }
} 

void mergeSort(int low, int high)
{
    int mid;
    if(low < high)
    {
        mid = (high + low) / 2;
        mergeSort(low, mid);
        mergeSort(mid + 1, high);
        merge(low, mid, high);
    } 
}

算法时间复杂度分析：

    递归和合并操作都是与n有关的函数，而且能构造递归树，所以采用递归式求解。

    整个代码的复杂度为：T(n) = 2 * T(n/2) + O(n)，然后通过展开求解

    如：T(n/2) = 2 * T(n/4) + O(n/2),

    上面两式合并：T(n) = 2 * [ 2 * T(n/4) + O(n/2) ] + O(n) = 2² * T(n/4) + 2 * O(n)

     由于递归树一共有lgn层。

     所以：T(n) = 2^lgn * T(1) + lgn * O(n) = nlgn