难度：基础。本题为归并排序的模板题（对应洛谷私题 U232725，题面自定）。考点是把归并排序完整写出来：先递归二分，再合并两个有序子数组，得到一个稳定、O(n log n) 的排序模板。

目标

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

• 独立写出归并排序的完整递归模板；
• 正确实现「合并两个有序子数组」的双指针过程；
• 处理 n = 10⁵ 规模的输入而不超时。

前置知识

• 递归与分治思想；
• 有序数组合并。

题目

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

输入格式

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

输出格式

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

数据范围

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

样例

样例输入

6
5 4 2 6 3 1

样例输出

1 2 3 4 5 6

样例解释

原序列 5 4 2 6 3 1 升序排列后为 1 2 3 4 5 6。

如何验证

先安装 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-05-merge-sort-template
pnpm lab:score -- labs/chapter-11/exercise/E-11-05-merge-sort-template

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

完成清单

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

思考题

1. 合并时用 a[i] <= a[j] 与 a[i] < a[j] 有什么区别？对稳定性有何影响？
2. 递归版归并排序与非递归（自底向上）版本有什么区别？各有什么优缺点？

题解

点击查看题解

思路

1. 递归边界：区间长度 ≤ 1 时天然有序；
2. 取中点把区间分成两半，分别递归排序；
3. 用双指针把两个有序子数组合并到临时数组，再写回原数组。

复杂度分析

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