假定有这样两个有序数组:
L1:{a1,a2,....an}
L2:{b1,b2,....bn}
简单归并，就是逐个比对，没有跳跃优化（skip）的。
最好的情况下，归并后的结果为{a1,a2,....an,b1,b2,...bn}或者{b1,b2,...bn,a1,a2...an}
比较的次数显然为n次。(n/2+n/2) ,出现前者或者后者的概率均为1/2
最坏的情况下，归并后的结果为{a1,b1,a2,b2....an,bn}或者{b1,a1,b2,a2,...bn,an}
不妨考察前者，L1或L2中任意一个（除bn以外）要想确定自己的位置，必须进行一次比较，因此总的比较次数为2n-1.
在考察平均情况：
假定归并后的结果为
{{b1,...br}{a1...an-1} || anbr+1...bn-1bn}
-----------------------------
这一块表示任意的b1..br共计r个来自L2的b序列，a1..an-1共计n-1个来自L1的a序列的数字组合成的一个串。
该串共计有C(r+n-1, r)种可能性。 这r+n-1个数每个数要想确定自己的位置都需要进行一次比较，因此比较次数是n+r次，而an和bn-r比，确定自己更小，还需要1次，因此总计的比较次数是n+r
归并后的结果总共有多少种可能呢？
相当于是C(2n,n),即在2n个L1序列中的元素和L2序列中的元素任意选n个。
其中bn排在最后的可能有C(2n,n)/2
{{b1,...br}{a1...an-1} || anbr+1...bn-1bn}这种情况（以bn做结尾）
因此在这种情况下的平均比较次数为
n-1
Σ (n+r)C(r+n-1,r)/(C(2n,n)/2) = 2n - 2n/(n+1)
r=0
平均的比较次数为(2n-2)/2 + (2n-2)/2 = 2n - 2 (最后一个可能是bn，也可能是an)
在平均情况下，比较次数只比最坏情况下少一次，这是不是很反直觉呢？可见归并中采用简单归并方法往往很低效。归并的方法在到排表求交中也会用到，以后再说。