此处C语言参考王道书，此外结合Go语言，一起理解

    “归并”的含义是将两个或者两个以上的有序表组合成一个新表，以下的例子都是二路归并为例子。

    Go 归并排序

    话不多少，先看Go语言版本的参考代码：

    1. package main
    3. import (
    4.     "fmt"
    5. )
    7. func main() {
    8.     s := []int{6, 7, 8, 10, 4, 6, 99}
    9.     res := mergeSort(s)
    10.     fmt.Println(res)
    11. }
    13. func mergeSort(s []int) []int {
    14.     len := len(s)
    15.     if len == 1 {
    16.         return s //最后切割只剩下一个元素
    17.     }
    18.     m := len / 2
    19.     leftS := mergeSort(s[:m])
    20.     rightS := mergeSort(s[m:])
    21.     return merge(leftS, rightS)
    22. }
    24. //把两个有序切片合并成一个有序切片
    25. func merge(l []int, r []int) []int {
    26.     lLen := len(l)
    27.     rLen := len(r)
    28.     res := make([]int, 0)
    30.     lIndex, rIndex := 0, 0 //两个切片的下标，插入一个数据，下标加一
    31.     for lIndex < lLen && rIndex < rLen {
    32.         if l[lIndex] > r[rIndex] {
    33.             res = append(res, r[rIndex])
    34.             rIndex++
    35.         } else {
    36.             res = append(res, l[lIndex])
    37.             lIndex++
    38.         }
    39.     }
    40.     if lIndex < lLen { //左边的还有剩余元素
    41.         res = append(res, l[lIndex:]...)
    42.     }
    43.     if rIndex < rLen {
    44.         res = append(res, r[rIndex:]...)
    45.     }
    47.     return res
    48. }

    代码还是很容易理解的,接下来看C语言版的。

    C语言版归并排序

    C语言由于没有来计算数组长度很好的函数，一般要标定数组的起始与结束的下标。
    已下参考王道书，

    ElemType *B = (Elmetype *)malloc((n+1)*sizeof(Elemtype));// 辅助数组 空间复杂度:O（n）
// 合并左右子列
void Merge(Elemtype A[],int low,int mid,int high)
{    int k;
    // 将数组B赋值
    for (int i = low ;i <= high;i++)
        B[i] = A[i];
    // B的左右子列比较，覆盖对应的A的位置
    for(int i = low,j = mid+1,k = i;i<=mid&&j<=high;k++)

        {if(B[i] > B[j])
                A[k] = B[j++];
          else
                A[k] = B[i++];
        }
    // 以上完成对于A的初步排序，若此时还有i或者j未到达最右端
    while(i<=mid) A[k++] = B[i++];
    while(j<=high) A[k++] = B[j++];    

    // 设置k是为了完善A的排序

}
// 递归深度logn,每趟的归并O(n),时间复杂度O(nlogn)
void MergeSort(Elemtype A[],int low,int high)
{
    if(low < high)
    {    int mid = (low+high)/2;
        MergeSort(A,low,mid);
        MergeSort(A,mid+1,high);
        Merge(A,low,mid,hign);   // 归并
    }

}