排序（4）：归并排序

对于待排序数组：{ 5, 2, 4, 6, 1, 3, 2, 6 }，归并算法的思路如上图，注意上图是从下往上看。

/* 把有序的 array[left]...array[mid] 和 array[mid+1]...array[right] 合并 */
void Merge(int array[], int temp[], int left, int mid, int right)
{
    int i = left;
    int j = mid + 1;
    int k = left;

    while (i <= mid && j <= right)
    {
        if (array[i] < array[j])
            temp[k++] = array[i++];
        else
            temp[k++] = array[j++];
    }

    while (i <= mid)
        temp[k++] = array[i++];
    while (j <= right)
        temp[k++] = array[j++];

    while (left <= right)
        array[left] = temp[left++];
}

/* temp[] 数组起到一个中转的作用 */
void MergeSort(int array[], int temp[], int left, int right)
{
    if (left >= right)
        return;

    int mid = ((right - left) >> 1) + left;

    MergeSort(array, temp, left, mid);
    MergeSort(array, temp, mid + 1, right);

    Merge(array, temp, left, mid, right);
}

Merge()耗时$O(n)$，则归并排序的时间递归式为$T(n)=2T(\frac n2)+O(n)$，解得$T(n)=O(nlogn)$。