【题目】

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

A. n^2
B. n log n
C. 2n
D. 2n-1

【解析（1）】

可以试着枚举。

当 n=1 时，一共2个数字，只需要比较1次。答案可能是 A/D 。
当 n=2 时，

答案选择：D

【解析（2）】

只要比较能进行到两个序列的最后一个数即可。

每次比较排好一个数，最后一次比较直接排好两个数。

所以最多的比较次数为：2n-1

答案选择：D