原理

    当采用纯归并方法对数组进行排序时，将数组进行划分，直到每个数组只剩下一个数字时，就停止划分；接着，对划分好的数组两两进行归并操作；直到所有的队列都归并完毕，归并排序就完成。

改进

归并排序大多和其他排序，比如：快速排序和插入排序一同使用。即，当归并的过程讲数组划分到一定程度的时候，采用快速排序或者插入排序，对每一个数据段进行排序，然后将排序好的数组归并起来，这样减少了归并的数组划分步骤和合并步骤，大大提高了排序的效率。

分析

归并排序过程中有数组的划分和归并的过程，所以其时间复杂度是O（nlog2n），其划分数组和归并数组的过程中，在原数组内部进行，故其空间复杂度是O（nlog2n）。

C语言实现

void merge_arr(int *arr, int begin, int mid, int end){    int a1_l = begin;    int a1_r = mid;    int a2_l = mid + 1;    int a2_r = end;    int *tmp = NULL;    int i = 0, k = 0;    if(NULL == arr || begin >= end ){        return ;    }    tmp = (int *)Malloc(sizeof(int) * (end - begin + 1));    while(a1_l <= a1_r && a2_l <= a2_r){        if(arr[a1_l] < arr[a2_l]){            tmp[i++] = arr[a1_l++];        }else{            tmp[i++] = arr[a2_l++];        }    }    while(a1_l <= a1_r){        tmp[i++] = arr[a1_l++];    }    while(a2_l <= a2_r){        tmp[i++] = arr[a2_l++];    }    for(k = 0; k < i; ++k){        arr[begin+k] = tmp[k];    }    free(tmp);}void part_arr(int *arr, int begin, int end){    int mid = 0;    if(NULL != arr && begin < end){        mid = begin + ((end - begin) >> 1);        part_arr(arr, begin, mid);        part_arr(arr, mid+1, end);        merge_arr(arr, begin, mid, end);    }}void merge_sort(int *arr, int begin, int end){    if(NULL == arr || begin >= end){        return;    }       part_arr(arr, begin, end);}