【题目】

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

A. \(n^2\)
B. \(n\lg{n}\)
C. \(2n\)
D. \(2n-1\)

【考点】

考察归并排序，可参考《大话数据结构》9.8节。

这题考的是比较次数，而不是时间复杂度或空间复杂度。

【解析】

先看看最好的情况：

设：
有序数组：\(A[4]={1,3,5,7}\)
有序数组：\(B[4]={8,10,12,14}\)
数组 \(C[8]\) 用来存储比较后的结果。

1与8比较，把1放到C中：\(C[]={1}\)
3与8比较，把3放到C中：\(C[]={1,3}\)
5与8比较，把5放到C中：\(C[]={1,3,5}\)
7与8比较，把7放到C中：\(C[]={1,3,5,7}\)
剩下的不用比较，直接放到C中：\(C[]={1,3,5,7,8,10,12,14}\)

共比较了4次，即n次。

再看看最坏的情况：

设：
有序数组：\(A[4]={1,3,5,7}\)
有序数组：\(B[4]={2,4,6,8}\)
数组 \(C[8]\) 用来存储比较后的结果

1与2比较，把1放到C中：\(C[]={1}\)
2与3比较，把2放到C中：\(C[]={1,2}\)
3与4比较，把3放到C中：\(C[]={1,2,3}\)
4与5比较，把4放到C中：\(C[]={1,2,3,4}\)
5与6比较，把5放到C中：\(C[]={1,2,3,4,5}\)
6与7比较，把6放到C中：\(C[]={1,2,3,4,5,6}\)
7与8比较，把7放到C中：\(C[]={1,2,3,4,5,6,7}\)
最后的8不用比较，直接放到C中：\(C[]={1,2,3,4,5,6,7,8}\)

共比较了7次，即2n – 1次。

参考：https://blog.csdn.net/haishu_zheng/article/details/80096986