NOIP 提高组初赛 · NOIP 2017 提高组初赛试题 第 11 题

设 $A$ 和 $B$ 是两个长为 $n$ 的有序数组，现在需要将 $A$ 和 $B$ 合并成一个排好序的 数组，请问任何以元素比较作为基本运算的归并算法最坏情况下至少要做 （ ）次比较。

这题考归并排序中最坏比较次数。拿到题先想：合并两个有序数组，每次比较最多只能把一个小元素放出去，最坏就是每次只放一个，直到只剩最后一个元素无需比较，所以是 2n-1。

很多同学会选 2n，误以为最后剩下的那个元素也要比较一次，其实它直接归位；还有人会选 n log n 或 n^2，那是排序算法的复杂度，不是合并两个已有序数组的比较次数，要分清场景。

考点概念：归并的两路合并

两个长为 n 的有序数组合并，最坏情况就是两序列元素完全交错（比如 A:1,3,5,... B:2,4,6,...），每次比较两个指针指向的元素，只能确定其中一个较小者可以输出，另一个指针不动。这样前 2n-1 个元素各需要一次比较才能确定位置，最后一个元素不用比较直接放入。

命题视角：为什么考这个？

命题人喜欢在这种基础算法题里挖“边界”坑：学生容易把“合并”和“排序”混为一谈，或者忘记“最后一个元素无需比较”这个关键细节。这道题就是专门测试你是否真正理解归并过程每一步的比较代价，而不是死记复杂度公式。