Mergesort Revisited MERGE-SORT(A,p.r) 1 if p<r 2 9=L(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 sequence 2 2 3 4 5 6 7 merge □ 2 5 12 6 Divide Conquer Combine merge merge Conquer □ 2 5 4 1 2 merge merge merge merge 回 回 回 回 6 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
cn cn T()= if n 1, 2T(/2)+cn Tn/2) Tn/2) cn Ig n cnlogn c/4 cn/4 cn/4 cn/4 aaann1e cn 确实比插入 排序效率高。 C n 这里似乎假设是2的整次幂,在我们涉 及的大多数情况下,这不影响结果
cnlogn 确实比插入 排序效率高。 T(n/2) T(n/2) 这里似乎假设n是2的整次幂,在我们涉 及的大多数情况下,这不影响结果