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!
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.
