原理

是一种基于分治策略的排序算法，包含“划分”和“合并”阶段。（先递归左子数组，再递归右子数组，最后处理合并。）

1. 划分阶段：通过递归不断地将数组从中点处分开，将长数组的排序问题转换为短数组的排序问题。
2. 合并阶段：当子数组长度为 1 时终止划分，开始合并，持续地将左右两个较短的有序数组合并为一个较 长的有序数组，直至结束。

示例

“2 4 1 0 3 5”

拆分阶段：

1. 首先将数组“2 4 1 0 3 5”拆分为两个子数组：“2 4 1”和“0 3 5”。
2. 继续拆分“2 4 1”为“2”和“4 1”，再将“4 1”拆分为“4”和“1”。
3. 拆分“0 3 5”为“0”和“3 5”，然后将“3 5”拆分为“3”和“5”。

排序与合并阶段：

1. 单个元素的子数组“2”、“4”、“1”、“0”、“3”、“5”本身就是有序的。
2. 合并“2”和“4”为“2 4”，因为 2 小于 4。
3. 合并“1”和前面的“2 4”，首先比较 1 和 2，1 小，结果为“1 2 4”。
4. 合并“0”和“3”为“0 3”。
5. 合并“5”和前面的“0 3”，先比较 5 和 0，0 小，再比较 5 和 3，3 小，结果为“0 3 5”。
6. 最后合并“1 2 4”和“0 3 5”，首先比较 1 和 0，0 小，结果为“0”，接着比较 1 和 3，1 小，结果为“0 1”，再比较 2 和 3，2 小，结果为“0 1 2”，继续比较 4 和 3，3 小，结果为“0 1 2 3”，最后比较 4 和 5，4 小，结果为“0 1 2 3 4 5”。

代码（C）

/* 合并左子数组和右子数组 */
void merge(int *nums, int left, int mid, int right) {
    // 左子数组区间 [left, mid], 右子数组区间 [mid+1, right]
    // 创建一个临时数组 tmp ，用于存放合并后的结果
    int tmpSize = right - left + 1;
    int *tmp = (int *)malloc(tmpSize * sizeof(int));
    // tmp 数组用于存储合并过程中的临时结果，避免在原数组上直接操作导致数据混乱。

    // 初始化左子数组和右子数组的起始索引
    int i = left, j = mid + 1, k = 0;
    // i 指向左子数组的当前元素，j 指向右子数组的当前元素，k 指向临时数组的当前位置。

    // 当左右子数组都还有元素时，比较并将较小的元素复制到临时数组中
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            tmp[k++] = nums[i++];
        } else {
            tmp[k++] = nums[j++];
        }
    }
    // 这个循环比较左右子数组的元素，将较小的元素放入临时数组。

    // 将左子数组和右子数组的剩余元素复制到临时数组中
    while (i <= mid) {
        tmp[k++] = nums[i++];
    }
    while (j <= right) {
        tmp[k++] = nums[j++];
    }
    // 如果左右子数组中有一个已经遍历完，另一个子数组可能还有剩余元素，将这些剩余元素直接复制到临时数组。

    // 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
    for (k = 0; k < tmpSize; ++k) {
        nums[left + k] = tmp[k];
    }
    // 将临时数组中的有序元素复制回原数组的对应位置，完成合并。

    // 释放内存
    free(tmp);
    // 释放临时数组占用的内存空间。
}

/* 归并排序 */
void mergeSort(int *nums, int left, int right) {
    // 终止条件
    if (left >= right)
        return; // 当子数组长度为 1 时终止递归
    // 如果子数组只有一个元素或者没有元素，说明已经有序，直接返回。

    // 划分阶段
    int mid = (left + right) / 2; // 计算中点
    mergeSort(nums, left, mid); // 递归左子数组
    mergeSort(nums, mid + 1, right); // 递归右子数组
    // 将数组不断划分为左右两个子数组，直到子数组长度为 1。

    // 合并阶段
    merge(nums, left, mid, right);
    // 当左右子数组都有序后，调用 merge 函数将它们合并为一个有序的数组。
}

复杂度

时间复杂度：

空间复杂度：为