一个有序数组和一个无序数组的进行整合排序,有什么高效的方法?该怎么解决

一个有序数组和一个无序数组的进行整合排序,有什么高效的方法?
一个数组A是有序的,一个数组B是无序的.需要按顺序排序为一个数组,
我能想到的就是先将无序B的用冒泡排序,再和A用归并排序,A,B的长度都不超过100

各位高手,还能提供更高效率的排序算法吗?
谢谢了.



------解决方案--------------------
考虑到数组A已经有序，可以遍历数组B中每一个元素，使用binary search的方法将元素插入到数组B中。这个算法的时间复杂度应该时O(N*log(N))。
------解决方案--------------------
MONOLINUX()
算法时间是 2*O(n)

-----------------------------------

哟
这不是咱们写搜索引擎的大牛嘛
连这么一个简单的问题都弄不明白?

基于比较的算法是O(nlogn)

给个简单的证明

如果存在低于O(nlogn)的算法
那么对于任何数组B,给一个已排序的A,我们可以得到一个合并A,B且已排序的数组C
去掉C中所拥有的A中的元素,这一步显然可以在O(n)内完成,那么我们就得到一个已排序的B,且得到一个复杂度低于O(nlogn)的基于比较的排序算法