GESP 八级 · GESP 202606 C++ 八级 第 6 题

归并排序每次把长度为 $n$ 的序列分成两个规模约为 $\frac{n}{2}$ 的子序列，递归排序后再用线性时间合并。该算法的时间复杂度通常为（ ）。

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】分治法｜递归复杂度分析｜排序算法

考纲定位：GESP 八级 C++ 大纲"数据结构与算法"模块明确将归并排序列为必掌握内容，命题人放这道题就是要卡住那些只背结论、不会分析递归结构的学生。

解题思维：看到归并排序，先想它的分治过程——每次把长度为 n 的序列分成两个规模约为 n/2 的子序列，递归排序后再用线性时间合并。递归深度是 log₂ n，每一层合并总代价是 O(n)，所以总时间 O(n log n)。这是分治法通法，能迁移到快速排序、归并排序等。

陷阱拆解：选项 A O(n) 是误以为合并是 O(log n) 或者忽略递归层数；B O(log n) 是把递归深度当成总代价；C O(n²) 是误以为每次合并是 O(n²)。命题人利用学生不熟悉递归树或分治复杂度推导。细节：题目说"递归排序后再用线性时间合并"，强调合并是 O(n)，但学生可能忽略递归层数。

反命题思维：如果把每次合并改成 O(n²) 会怎样？答案会变成 O(n² log n) 或 O(n²)。提醒刷到类似题先问命题人想考什么——是递归深度还是合并代价。