导出递归式 MERGE-SORT (A,p,r) 1 if p<r 2 q=(p+r/2 两次递归，理想情 况下每次问题规棋 3 MERGE-SORT(A,p.q) 是原来的一平。 4 MERGE-SORT(A,q大L,r) 5 MERGE(A,p,q,r) 井递归开结 Θ(1) ifn=1 T)= 2T(n/2)+Θ(n)ifn>1导出递归式 两次递归，理想情 况下每次问题规模 是原来的一半。 非递归开销