CSP-S 2019 第一轮 第11题：设 A 和B 是两个长为n的有序数组，现在需要将A和 B合并成一个排

题目

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

选项

• A. $n^2$
• B. $n \log n$
• C. $2n$
• D. $2n - 1$

答案

D

题解

选 D．\(2n-1\)。

要证明“最坏情况下至少”，需要说明两点：

1. \(2n-1\) 次足够。

用双指针归并，每次比较两个数组当前最小的元素，将较小者放入结果。一旦某个数组取完，另一个数组剩下的元素直接接上。因此，合并 \(2n\) 个元素最多比较 \(2n-1\) 次。

1. 最坏情况下不能更少。

考虑两个数组的元素恰好交错： \[ A_1<B_1<A_2<B_2<\cdots<A_n<B_n. \] 最终序列中有 \(2n-1\) 对相邻元素，且每一对都来自不同数组。每对都必须直接比较：若某对没有比较过，交换这两个相邻元素的大小关系，两个原数组仍各自有序，其他比较结果也不变，算法便无法确定它们的正确顺序。

所以，任何基于元素比较的归并算法，最坏情况下都至少需要 \(2n-1\) 次比较。