难度：进阶。题目原型为 AOJ ALDS1_5_B Merge Sort。本题的考点是在归并排序的合并阶段统计比较次数：除了把数组排好，还要记录排序过程中一共比较了多少次，理解归并排序每一层做了多少工作。

目标

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

• 用归并排序完成排序，并输出排序结果；
• 正确统计合并过程中的比较次数；
• 说明「比较次数」的定义如何随实现方式（哨兵 vs. 显式拷贝）变化。

前置知识

• 归并排序的递归与合并过程；
• 双指针合并两个有序数组。

题目

读入 n 和 n 个整数，用归并排序把它们从小到大排序，输出排序后的数组与归并过程中的比较次数。

输入格式

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

输出格式

• 第一行：排序后的 n 个整数，从小到大排列，相邻整数用一个空格隔开；
• 第二行：一个整数，表示归并排序过程中的比较次数。

数据范围

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

样例

样例输入

10
8 5 9 2 6 3 7 1 10 4

样例输出

1 2 3 4 5 6 7 8 9 10
34

样例解释

序列 8 5 9 2 6 3 7 1 10 4 归并排序后为 1 2 3 4 5 6 7 8 9 10。采用「哨兵 + 每次写入计一次比较」的计数方式时，整个归并过程共比较 34 次。

如何验证

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

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

完成清单

• 样例输出与题目一致（排序结果 + 比较次数 34）
• 升序、降序、含重复值、单个元素四种情况都通过
• 能解释「比较次数」在你的实现里是在哪里累加的

思考题

1. 采用哨兵写法时，比较次数为什么等于「所有合并操作写入元素的总次数」？
2. 如果改用 while 循环 + 显式拷贝剩余元素的写法，比较次数会如何变化？会不会比哨兵写法少？

题解

点击查看题解

思路

1. 用归并排序递归二分区间，合并两个有序子数组；
2. 合并时给左右两段各加一个「无穷大」哨兵，使两段都不会先耗尽；
3. 每写入一个元素都先做一次 L[i] <= R[j] 的比较，累加计数。

复杂度分析

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