归并：把俩个或多个已经有序的序列合并成一个。
二路归并：每选出一个小元素就需对比关键字1次
多路归并：每选出一个小元素就需对比关键字(n-1)次
对于二路归并排序：形似倒立的二叉树

• 1.二叉树的第h层最多有2^h-1个结点，若树高为h，则应满足n ≤ 2^h-1，即h-1 = ^┌log₂n^┐
  结论：n个元素进行2路归并排序，归并趟数=^┌log₂n^┐
• 2.每趟归并时间复杂度为O(n)，则算法时间复杂度为O(nlog₂n)
• 3.空间复杂度=O(n)，来自辅助数组temp
• 4.稳定性：稳定

代码实现：

// 辅助数组
int *temp = (int *)malloc(ArrSize*sizeof(int));
// mid分开的俩组各自有序，将俩部分归并
void MergeArr(int arr[], int low, int mid, int high){
    int i,j,k;
    for(k=low; k<=high; k++){
        temp[k] = arr[k];
    }
    for(i=low, j=mid+1,k=i; i<=mid && j<=high; k++){
        if(temp[i] <= temp[j]){
            arr[k] = temp[i++]; // 将较小值复制到arr中
        }else{
            arr[k] = temp[j++];
        }
    }
    while(i <= mid){
        arr[k++] = temp[i++];
    }
    while(j <= high){
        arr[k++] = temp[j++];
    }
}

// 归并排序
void MergeSort(int arr[], int low, int high){
    if(low < high){
        int mid = (low+high)/2; // 从中间划分
        MergeSort(arr, low, mid);   // 对左分区归并排序
        MergeSort(arr, mid+1, high);   // 对右分区归并排序
        MergeArr(arr, low, mid, high)
    }
}

总结

归并排序中在递归调用那块代码可能不好理解，在MergeSort中第三行和第四行代码分别是对由mid相分的俩个区间进行分别递归，最后在递归的最底层只是比较俩个数据，最后跳出递归。