GESP 五级 · GESP 202312 C++ 五级 第 16 题

归并排序的时间复杂度是 $O(N \log N)$。

这题就是考经典结论，拿到题直接回想归并排序的‘分治’流程：一层层二分到底（深度 logN），每层合并都要扫一遍（工作量 N），相乘就是 O(N log N)，选 A 没错。

最容易错的是把归并排序当成冒泡或选择排序，脑子里一出现‘排序’就下意识想 O(N²)；或者误以为合并两个有序数组要 O(N²) 去两两比对，其实只要线性扫描就能完成合并；还有人纠结最坏/平均/最好情况，以为归并排序会有波动，其实它的复杂度是稳如泰山的，无论输入如何都是 O(N log N)。

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

命题人借 O(N log N) 考查考生对经典排序算法复杂度的记忆与理解，这是五级算法模块的必考内容，卡住的是大量只背结论、不懂推导过程的学生。

归并排序核心是‘分治’：将数组不断二分至长度为 1，再自底向上合并有序子数组。合并过程需遍历当前所有元素，故每层耗时 O(N)；递归深度为 log₂N，总时间复杂度即为 O(N log N)。记住‘分治 + 线性合并=对数深度×线性工作’这一模式，可快速判断类似分治算法（如快速排序、堆排序）的复杂度。

错误选项 B 往往源于混淆概念。命题人设陷阱有三：一是将归并排序与冒泡/选择排序的 O(N²) 复杂度混为一谈；二是误以为合并步骤本身是 O(N²)（实际合并两个有序数组只需线性扫描）；三是过度纠结于最坏/平均/最好情况——归并排序无论输入如何，时间复杂度恒为 O(N log N)。若只背‘归并排序快’而不理解‘分治 + 线性合并’的本质，极易掉入 O(N²) 或 O(N) 的陷阱。

若把题目改为‘归并排序的空间复杂度是 O(log N)’，答案即变错（实际需 O(N) 额外空间用于合并）；若改为‘快速排序平均时间复杂度是 O(N log N)’，答案又变对。这类题的本质不是考记忆，而是考你是否能透过现象（‘快’）看清本质（‘分治 + 线性合并’）。下次遇到任何算法复杂度判断题，先问自己：这个算法是否用了分治？如果是，合并/递归层数是多少？

从历年数据看，归并排序在题库共考过 51 题，覆盖 6 个考试级别（2009-2026），其中 GESP 五级考了 33 题，占比超过六成，说明这是五级考生的高频考点。逐年分布上，2023 年考了 6 题，2024 年激增至 14 题，2025 年达到 15 题的峰值，2026 年回落至 9 题，呈现出明显的‘近五年高频爆发’趋势。分赛事来看，除了 GESP 五级，GESP 八级也考了 8 题，CSP 提高级考了 3 题，说明随着级别提升，对分治算法的考察并未减弱，反而更偏向于在更复杂场景下检验基础。

基于这些数据，可以预测未来归并排序及其变体（如空间优化版、与快速排序对比题）仍将是 GESP 五级和八级的重点，命题人可能会在 2026 年及以后继续维持较高频次，甚至结合‘空间复杂度’或‘稳定性’出题，以区分只会背公式的学生。因此，掌握分治思想不仅是为了做对这一题，更是为了应对未来更灵活的考查方式。