GESP 五级 · GESP 202503 C++ 五级 第 22 题

归并排序算法的时间复杂度与输入是否有序无关，始终稳定为 $ O(n \log n) $。

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

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

【考点】分治法｜排序算法复杂度｜O(n log n)

---

1. 🎯 考纲定位

GESP 五级《排序算法》模块，与递推、递归并列考查。命题人卡住大量学生只背结论、不究原理的弱点——以为排序算法复杂度会随数据状态变化，属基础概念盲区。

2. 🧠 解题思维

归并排序核心是“分治”：无论输入是否有序，每次都将数组两等分，递归排序后合并。合并过程耗时固定为 O(n)，递归层数固定为 O(log n)，故总复杂度恒为 O(n log n)。这一类“复杂度与数据状态无关”的题，本质是考察算法的“最坏/平均/最好”三种情况是否一致。

3. 🪤 陷阱拆解

错误选项设计逻辑：混淆“归并排序”与“快速排序”——快速排序最坏 O(n²) 而平均 O(n log n)，容易让人误以为排序算法复杂度会随数据状态变化。题目最阴险的细节是“稳定”一词，若只背结论，会错误联想到“插入排序在有序数据下稳定为 O(n)”，从而误选 B。

4. 🔄 反命题思维

若将题中“归并排序”换成“快速排序”，命题必错；若换成“堆排序”则正确。刷到此类题先问：该算法的三种情况复杂度是否一致？不一致则必错。

---

()