归并排序作为最经典的分治算法之一，本质是利用递归把问题分解至最小子问题（即将原数组分解为只有单个元素的子数组），然后递归开始“回升”，每一层回升都是在合并两个有序数组（依次从两个数组的头部取出较小的元素放入目标数组，某一组全部取出后即可直接依次插入另一数组的所有剩余元素，两组元素全部取完后排序结束），C语言代码如下：

void merge(int arrA[], int lenA, int arrB[], int lenB, int arrTarget[]) {    int iA = 0, iB = 0, iT = 0;    for (; iA < lenA && iB < lenB; iT ++) { // 当两个数组都还有剩余元素时，比较每一个元素并插入        if (arrA[iA] <= arrB[iB]) {            arrTarget[iT] = arr[iA];            iA ++;        } else {            arrTarget[iT] = arr[iB];            iB ++;        }    }    for (; iA < lenA; iA ++, iT ++) arrTarget[iT] = arrA[iA]; // 若数组A还有剩余元素    for (; iB < lenB; iB ++, iT ++) arrTarget[iT] = arrA[iB]; // 若数组B还有剩余元素}

完成了这个merge，其实就已经做完了归并排序的大部分工作，接下来我们只要把前期准备做好就可以了！也就是merge接受的两个输入数组必须是有序的，但是怎么才能从乱序的原始数组中得到两个有序的子数组呢？

void mergeSort(int arr[], int fst, int lst, int arrTarget[]) {    if (fst < lst) {        // 二分（此处的函数将会在子数组的fst不大于lst时开始逐层返回，进行合并）        int mid = (fst + lst) / 2;        mergeSort(arr, fst, mid, arrTarget);        mergeSort(arr, mid + 1, lst, arrTarget);        // 合并        merge(arr + fst, mid - fst + 1, arr + mid + 1, lst - mid, arrTarget + fst);    }}

运行结束后，arrTarget就是原数组的有序版本，它可以在main函数中直接定义,不过也可以通过进一步打包函数来避免这种麻烦并减少需要填写的参数：

int* MergeSort(int arr[], int len) {    int* arrTarget = (int*)malloc(sizeof(int) * len);    // 此处不建议直接创建数组，函数结束后所有临时变量的内存都将被释放，任何操作都可能改变这里的数据    if (arrTarget == NULL) { // 内存申请失败        printf("Error: malloc failed.\n");        exit(1);    }    mergeSort(arr, 0, len - 1, arrTarget);    return arrTarget;}

现在只需要填上原始数组和长度就可以得到一个排好序的新数组的指针啦！