Question

Just finished watching lecture#9 and I'm having troubles understanding why merge_sort algorithm has O(nlogn) efficiency.
I can't understand the logn factor which is related to the number of calls to function merge().
Let me illustrate it with n=8 example (n being the length of the list):

sort[4,1,2,0,3,7,6,5], recursively splits into two calls of sort():

sort[4,1,2,0] + sort[3,7,6,5], and so on:

sort[4,1] + sort[2,0] + sort[3,7] + sort[6,5]

sort[4] + sort[1] ...........................+ sort[5]

According to sort() algorithm the singletons don't require merge() so the number of calls to this function is equal to the number of calls to sort(L) when L has length > 1. In this example there are exactly n-1 calls to sort(L) with len(L)>1, hence n-1 calls to merge(), and this seems to be true for any n.
However it can't be because n-1 is linear and the efficiency of merge_sort algorithm would be O(n^2).
So where am I going wrong? I just hope it's not too obvious.

Thanks

Answer 1

before sorting:
sort[4,1,2,0,3,7,6,5], recursively splits into two calls of sort():

sort[4,1,2,0] + sort[3,7,6,5], and so on:

sort[4,1] + sort[2,0] + sort[3,7] + sort[6,5]

sort[4] + sort[1] ...........................+ sort[5]

as we sort, each merge is called on pairs lists

sorting:
sort[4] + sort[1] ...........................+ sort[5]
(merge called once)
sort[1,4] + sort[0,2] + sort[3,7] + sort[5,6]
(merge called twice)
sort[0,1,2,4] + sort[3,5,6,7]
(merge called thrice)
sort[0,1,2,3,4,5,6,7]

total merges: 3=log_2(8)

Answer 2

Thanks for the reply, TuringTest.

When you say "merge called once", merge it's actually called four times for lists of total size 2 (sum of left and right lists) or n/4. Is it ok to say that 4 calls to merge a list of total length n/4 is the same as one call to merge a list of total size n?

If so, then the 7 calls to merge in the stated example are:
4 merges of size n/4 + 2 merges of size n/2 + 1 merge of size n,
which would be equivalent to 3 merges of size n thus explaining the logarithmic growth.

Maybe that's the detail I'm missing. In lecture prof. Guttag mentions the number of calls to merge() but maybe the focus should be on the "equivalent calls" of size n.

If this is not it yet I guess I'll just have to try again :)