Question

Is the mergesort algorithm in lecture 10 really n*log(n)? I get that the dividing part is log(n), but it seems that the merge itself should be O(n*Iog(n)), making the whole algorithm n((log(n))^2). Let's say you take an 8 membered list. Sorting the singleton level takes 4 steps, then the next level takes 6 steps, then the next level takes 7 steps. This is a linear algorithm??? The number of levels should be log(n), and the worst case time to run through a level is n-1. This sounds like the merge is nlog(n), not the mergesort. The mergesort should be n((log(n))^2). Am i missing something?

Answer 1

Hey . maybe this would help

http://www.youtube.com/watch?feature=player_detailpage&v=JPyuH4qXLZ0#t=3814s

Answer 2

I get how merging one level takes O(n) time. But you're not just merging the elements of the list once... you're merging them log(n) times. That's why it seems like mergesort should be n((log(n))^2). There's an extra log(n) to account for the fact that you're merging all the elements log(n) times. Can someone explain to me why this isn't true?

Answer 3

i get it now... i wasn't realizing that the merge algorithm is run once for every division in the mergesort algorithm. Effectively 1 n-time for each of log(n) divisions. I was somehow thinking that the *entire* merge of the whole tree ran for each of log(n) divisions.