归并排序MergeSort的C实现

归并排序作为最经典的分治算法之一，本质是利用递归把问题分解至最小子问题（即将原数组分解为只有单个元素的子数组），然后递归开始“回升”，每一层回升都是在合并两个有序数组（依次从两个数组的头部取出较小的元素放入目标数组，某一组全部取出后即可直接依次插入另一数组的所有剩余元素，两组元素全部取完后排序结束），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接受的两个输入数组必须是有序的，但是怎么才能从乱序的原始数组中得到两个有序的子数组呢？
这里我们可以使用二分法，也就是将原始数组从中点开始不断往下分割，当每一个子数组都只包含一个元素时，它也就达到了有序状态。而这里，自然也就是递归开始“回升”的节点，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;
}

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