归并排序

思路

分治法
将数组分成A、B两组，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？

可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。

代码

//将两个有序数组合并成一个有序数组
void merge(int a[], int begin,int mid,int end,int b[]) {
    int i = begin;
    int j = mid + 1;
    int k = 0;
    while ((i <= mid) && (j <= end)) {
        if (a[i] < a[j]) {
            b[k] = a[i];
            k++;
            i++;
        }
        else{
            b[k] = a[j];
            k++;
            j++;
        }
    }
    while (i<=mid){
        b[k] = a[i];
        k++;
        i++;
    }
    while (j <= end){
        b[k] = a[j];
        k++;
        j++;
    }
    for (int i = 0; i < k; i++){
        a[begin + i] = b[i];
    }
}
//归并排序
void MergeSort(int a[], int begin,int end,int b[]) {
    if (begin < end) {
        int mid = (begin + end) / 2;
        MergeSort(a, begin, mid, b);
        MergeSort(a, mid + 1, end, b);
        merge(a, begin, mid, end, b);
    }
}

时间复杂度

最坏情况$O(n\log(n))$
平均情况$O(n\log(n))$