Time Complexity of Merge Sort
T(n) = 2*T(n/2)+n+1
O(nlogn)
sort(int a, int lb, int ub){
int m;
if (lb>=ub) return;
m = (lb+ub)/2; /* O(1) */
sort(a,lb,m);
sort(a,m+1,ub);
merge(a,lb,m,ub); /* O(n) */
}
Previous slide
Next slide
Back to first slide
View graphic version