AcWing 787. 归并排序

◎

本节目标

递归排序两个半区并稳定合并，得到严格的 O(n log n) 排序。

这道题把排序与选择中的分治思想落实为“先让两个半区有序，再线性合并”。

查看 AcWing 原题

题意与约束

给定一个整数数组，输出从小到大的结果。n = 1 时数组本身已经有序，是递归的基础情形。

朴素思路与瓶颈

逐个选择剩余最小值需要反复扫描未排序部分，最坏时间为 O(n²)。归并排序先递归得到两个有序半区，再用一次线性合并完成当前区间，从而把总时间稳定在 O(n log n)。

左右区间为何已经有序

对 [left, right] 取中点 mid，先递归排序 [left, mid] 和 [mid + 1, right]。两次递归返回时，两个半区各自都有序；此时不必在半区内部再次比较，只需比较它们尚未取走的最小元素。

双指针 i、j 分别指向左右半区。每次把较小值写入 tmp，其余未写元素都不可能比它更小。相等时先取左值，因此保留原有相对顺序，合并是稳定的。

临时数组的范围

临时数组只保存当前 [left, right] 的合并结果。任一半区耗尽后，直接复制另一半剩余元素，最后只回写这一段区间；不要错误地把其他递归层的内容也覆盖掉。

代码实现

C++ 使用全局 n、nums 和 tmp，递归函数 mergeSort(left, right) 只描述当前区间；tmp 在入口按 n 初始化一次，并在所有递归层复用。Python 在顶层函数中创建一次临时数组，再通过参数显式传给递归函数。两种核心函数都不读取输入，入口仅处理标准输入输出。

C++

C++17

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<int> nums;
vector<int> tmp;

void mergeSort(int left, int right) {
    if (left >= right) {
        return;
    }

    const int mid = left + (right - left) / 2;
    mergeSort(left, mid);
    mergeSort(mid + 1, right);

    int i = left;
    int j = mid + 1;
    int pos = left;
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            tmp[pos++] = nums[i++];
        } else {
            tmp[pos++] = nums[j++];
        }
    }
    while (i <= mid) {
        tmp[pos++] = nums[i++];
    }
    while (j <= right) {
        tmp[pos++] = nums[j++];
    }
    for (int k = left; k <= right; k++) {
        nums[k] = tmp[k];
    }
}

int main() {
    cin >> n;
    nums.resize(n);
    tmp.resize(n);
    for (int& x : nums) {
        cin >> x;
    }

    mergeSort(0, n - 1);
    for (int i = 0; i < n; i++) {
        if (i > 0) {
            cout << ' ';
        }
        cout << nums[i];
    }
    return 0;
}

Python

Python 3

import sys


def _merge_sort_range(nums: list[int], tmp: list[int], left: int, right: int) -> None:
    if left >= right:
        return

    mid = left + (right - left) // 2
    _merge_sort_range(nums, tmp, left, mid)
    _merge_sort_range(nums, tmp, mid + 1, right)

    i = left
    j = mid + 1
    pos = left
    while i <= mid and j <= right:
        if nums[i] <= nums[j]:
            tmp[pos] = nums[i]
            i += 1
        else:
            tmp[pos] = nums[j]
            j += 1
        pos += 1
    while i <= mid:
        tmp[pos] = nums[i]
        i += 1
        pos += 1
    while j <= right:
        tmp[pos] = nums[j]
        j += 1
        pos += 1
    nums[left : right + 1] = tmp[left : right + 1]


def merge_sort(nums: list[int]) -> None:
    if nums:
        _merge_sort_range(nums, [0] * len(nums), 0, len(nums) - 1)


def main() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    nums = data[1 : n + 1]
    merge_sort(nums)
    print(*nums)


if __name__ == '__main__':
    main()

复杂度分析

• 时间复杂度：O(n log n)。每层合并总共处理 n 个元素，共有 log n 层。
• 空间复杂度：O(n)，用于临时数组；递归栈为 O(log n)。

易错点

• 中点两侧必须是 [left, mid] 与 [mid + 1, right]。
• 合并后要回写当前区间。
• 相等时取左值才能保持稳定性。

模式迁移

归并的价值在于利用两个有序来源做线性处理。后续的逆序对、两个有序数组合并和外部排序，都复用“已排序半区 + 双指针”的结构。