Question

有序表归并~

当将两个长度均为n的有序表A=（a1，a2，…，an）与B=（b1，b2，…，bn）(ai≠bj,
1≤i,j≤n)归并为一个有序表C=（c1, c2,…,c2n）时，所需进行的元素比较次数最少可达n,最多可达2n-1。
（1）假设有序表C=（2，4，5，6，7，9），试举出两组A与B的例子，使它们在归并过程中进行的元素比较次数分别达到最少和最多；
（2）写出一般情况下，使归并所需进行的元素比较次数分别达到最少和最多时，A与B中的元素应满足的条件。

Answer 1

（1）最少 A=（2,4,5）B=(6,7,9) 最多 A=(2,5,7) B=(4,6,9)
（2）最少时满足一个序列中的最大值小于令一个序列中的最小值；
最多时的情况是两个序列在最终的序列中一个取奇数元素，一个取偶数元素。