Mergesort revisited MERGE-SORT(A P, r) I ifp<r 2q=|(p+r)/2」 3 MERGE-SORT(A, P, q) 4 MERGE-SORT(A, q+1,r) 5 MERGE(A, P, q, r) 问题1 这个算法究竟是如何“排”序的?
Mergesort Revisited
sorted soquence 7 34567 marge 4 23 C Divide conquer Combine rge merge conquer merge merge merge nLe initial sequence
5 2 4 7 1 3 2 6 5 2 4 7 1 3 2 6 Divide Divide further, until… Conquer Combine Divide Conquer
导出递归式 MERGE-SORT(A, P, r) <r 2345 q=(0+)2 两次归,理想情 况下条次问题规棋 MERGE-SORT(A, P,9) 是原来的一。 MERGE-SORT(A, 9+1, r) MERGE(A, P,q,r) 非逼归开萄 ifn=I =1x02+6051
导出递归式 两次递归,理想情 况下每次问题规模 是原来的一半。 非递归开销
C ifn=1 CT(n/2)+cn ifn>I T2) T(n/2)mmmmmmmmilin.CI Ig n cologne m/4 14 cn/4 cn/4 mil cn 确实比插入 排序效率高。 nl 这里似乎假设n是2的整次幂,在我们涉 及的大多数情况下,这不影响结果
cnlogn 确实比插入 排序效率高。 T(n/2) T(n/2) 这里似乎假设n是2的整次幂,在我们涉 及的大多数情况下,这不影响结果