1

After the lecture, I still do not quite understand why the upper bound of mergesort is n log n. I've tried to connect it with the phone book problem, which helped a little, but still don't really get it.

And is the log in log n base 10 or 2? It seems that 2 makes more sense since we always have to cut the sequence in the half and then do the sorting on both sides, but I'm just not sure.

Thanks!

1

Merge sort consists of two main parts — diving part and merging part.

In the dividing part, the n-element array gets divided into two halves, and the halves into halves, ... until you have n one-element arrays.

As n grows, the number of steps to complete this process grows logarithmically. In this case, log base 2 of n (or just log n). Ex: it would take you 3 steps to divide an 8-element array and 4 steps to divide 16-element array.

Then comes the merge part in which each two halves get merged together. The number of steps to accomplish this task grows proportionally to n as n grows. So the runtime of this process is linear — O(n). Ex: if each half is 2-element long, it would take you typically 3 (i.e., n - 1 or roughly n steps, ignoring the -1) while it would take you roughly 8 steps to merge two 4-element arrays.

This process happens at every level (i.e., every step) of the dividing part.

Recall that the runtime of the latter is log n. This gives a total of n log n.

| improve this answer | |

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .