分治策略

　　算法参考了度娘：归并排序

#include <stdio.h>

static void Merge();
void MergeSort();

static void Merge(int arr[], int tempArr[], int arrBase, int arrMid, int arrTop)
{
    int i = arrBase, j = arrMid + 1, k = arrBase;

    while(i != arrMid + 1 && j != arrTop + 1)
    {
        if(arr[i] > arr[j])
            tempArr[k++] = arr[j++];
        else
            tempArr[k++] = arr[i++];
    }
    while(i != arrMid + 1)
        tempArr[k++] = arr[i++];
    while(j != arrTop + 1)
        tempArr[k++] = arr[j++];
    for(i = arrBase; i < arrTop + 1; i++)
        arr[i] = tempArr[i];
}

void MergeSort(int arr[], int tempArr[], int left, int right)
{
    int mid;

    if(right > left)
    {
        mid = (left + right)/2;
        MergeSort(arr, tempArr, left, mid);
        MergeSort(arr, tempArr, mid + 1, right);
        Merge(arr, tempArr, left, mid, right);
    }
}

int main()
{
    int nums[] = {6, 5, 4, 3, 2, 1}, array[sizeof(nums)/sizeof(int)];
    int i;

    MergeSort(nums, array, 0, sizeof(nums)/sizeof(int) - 1);

    for(i = 0; i < sizeof(nums)/sizeof(int); i++)
        printf("%d ", nums[i]);
    printf("
");
    return 0;
}

　　递归＋循环的算法，时间复杂度为Θ(nlgn)。证明可参考递归式：

T(1) = 1                N = 1;
T(N) = 2T(N/2) + N      N > 1;

　　证明：

对递归式除以N：
T(N)/N = T(N/2)/(N/2) + 1
T(N/2)/(N/2) = T(N/4)/(N/4) + 1
...
T(2)/2 = T(1)/1 + 1

利用累加法可得：
T(N)/N = T(1) + logN(注意到共有logN项，所以是logN个1相加)

整理一下式子，最后可得：
T(N) = N + NlogN = O(NlogN)

证毕.