难度：基础。题目原型为洛谷 P1177【模板】排序。本题的考点是用归并排序实现 O(n log n) 的排序：把数组不断二分到单个元素，再合并两个有序子数组，用分治代替朴素排序。

目标

完成本题后，你应该能够：

• 写出归并排序的递归模板（二分 + 合并）；
• 说明归并排序为什么是 O(n log n)，且是稳定的；
• 处理 n = 10⁵ 规模、|a[i]| = 10⁹ 量级的整数输入。

前置知识

• 递归的基本概念；
• 两个有序数组合并成一个有序数组的过程。

题目

读入 n 和 n 个整数，把它们从小到大排序后输出一行。

输入格式

• 第一行一个整数 n；
• 第二行 n 个整数，表示待排序序列 a。

输出格式

一行 n 个整数，从小到大排列，相邻整数用一个空格隔开。

数据范围

项目	范围
序列长度 n	1 ≤ n ≤ 10⁵
元素值	−10⁹ ≤ a[i] ≤ 10⁹

样例

样例输入

5
4 2 4 5 1

样例输出

1 2 4 4 5

样例解释

原序列 4 2 4 5 1 升序排列后为 1 2 4 4 5，其中 4 出现了两次，两个 4 相邻输出。

如何验证

先安装 Node.js、pnpm 和支持 C++17 的编译器。

# 已进入本 Lab 目录
make doctor
make run
make run CASE=001-sample
make interactive
make score

Windows 没有安装 Make 时，在仓库根目录使用等价的 pnpm 入口：

pnpm lab:run -- labs/chapter-11/exercise/E-11-04-sort-template
pnpm lab:score -- labs/chapter-11/exercise/E-11-04-sort-template

标准输出参与判题，调试信息请写入标准错误。

完成清单

• 样例输出与题目一致
• 升序、降序、含重复值、单个元素四种情况都通过
• 能说出归并排序的时间复杂度与稳定性

思考题

1. 归并排序为什么是稳定的？a[i] <= a[j] 中的等号放到哪一侧会影响稳定性吗？
2. 归并排序需要 O(n) 的辅助数组，这个空间能不能省到 O(1)？

题解

点击查看题解

思路

归并排序分两步：

1. 递归地把 [l, r] 二分，直到子数组只有一个元素（天然有序）；
2. 合并两个有序子数组：用双指针分别从两段头部扫描，每次取较小者放入临时数组，最后写回原数组。

复杂度分析

• 时间复杂度：O(n log n)；
• 空间复杂度：O(n)（辅助数组）。