6. 归并排序

归并排序：算法时间复杂度O(nlogn) 空间复杂度O(n)

算法实现

#include <iostream>

using namespace std;

void merge(int * a, int start, int mid, int end)
{
    int i = start, j = mid + 1;
    int m = mid, n = end;

    int tmp[20];
    int k = 0;
    while(i <= m && j <= n)
    {
        if(a[i] <= a[j])
            tmp[k++] = a[i++];
        else
            tmp[k++] = a[j++];
    }

    while(i <= m)
        tmp[k++] = a[i++];

    while(j <= n)
        tmp[k++] = a[j++];

    for(int i = 0; i < k; ++i)
        a[start+i] = tmp[i];
}

void mergeSort(int * a, int start, int end)
{
    if(start < end)
    {
        int mid = (start+end)/2;

        mergeSort(a, start, mid);
        mergeSort(a, mid+1, end);
        merge(a, start, mid, end);
    }
}

int main()
{
    int a[10] = {52,12,36,14,48,69,57,89,45,16};

    mergeSort(a, 0, 9);

    for(int i = 0; i < 10; ++i)
        cout << a[i] << " ";

    cout << endl;

    return 0;
}