How to calculate the mergesort time complexity?

Question

Recently while reading a book (Skienna) I came across the following statement:

Mergesort works by dividing nodes in half at each level until the number of nodes becomes 1 hence total number of times we would need to do this would be $\lceil\log_{2}{n}\rceil$ and for each level we perform $O(n)$ work hence total time taken will be $O(n \log n)$

How to understand the above statement? Also, I am always confused about when to take ceil or floor. I am not a math major therefore it seems intimidating to me at first. I don't know about generating functions etc.

Answer 1

Imagine that we have an array $A$ of size $n$. Mergesort splits this array into two equal halves and sorts them individually. So in context of the paragraph you have provided, each node corresponds to some chunk of the original array that we want to sort. We divide a node $A[L,R]$ to two nodes $A[L,M]$ and $A[M+1,R]$ with $M = \frac{L+R}{2}$

The splitting of a node $A[L,R]$ into two nodes takes $R-L+1$ time and then merging the two child nodes $A[L,M]$ and $A[M+1,R]$ again takes $A[R-L+1]$ time. Thus for every node, the number of operations the algorithm performs is equal to twice the size of the array corresponding to that node.

Thus we have that on any particular level if we have an array of size $k$, splitting and merging of the array can be done in $k + 2\times \frac{k}{2} = 2k$ operations.

Now note that we keep splitting the array till we have arrays of size $1$ since we can't split them further.

Draw a binary tree with the root node corresponding to the array $A[1,N]$ and with each node having two children corresponding to its left and right halves and recursively draw the structure for each child till we have arrays of size $1$. Denote each node by the size of the array that it corresponds to. We will get something that looks like this

(Taken from Khan Academy)

This is the recursion tree for merge sort.

The computation time spent by the algorithm on each of these nodes is simply two times the size of the array the node corresponds to. Therefore the total running time $S$ of mergesort is just the sum of all the sizes of the arrays that each node in the tree corresponds to i.e. $$S = 2 \sum_{i=0}^k 2^i\frac{n}{2^i}$$

(How did we get this sum? There are $2^i$ nodes of size $\frac{n}{2^i}$ in the tree and it takes $2k$ time to finish computation on an array of size $k$)

Observe that when $i=k$, $\frac{n}{2^k} = 1 \implies n = 2^k \implies k = \lceil{\log n}\rceil$ Thus $S$ reduces to $$2 \sum_{i=0}^{\lceil{\log n}\rceil} n = 2n\lceil{\log n}\rceil = \mathcal{O}(n\log n)$$

Answer 2

The response of Banach is quite precise, here is a description how to imagine merging sort as splitting sequence into halves and watching them as a binary tree.

Consider the sequence of $ n $ elements. First step divides the sequence into two groups of $ \frac{n}{2} $ elements. The second step divides those two groups into four groups of $ \frac{n}{4} $ elements. Third step divides these four groups into eight groups of $ \frac{n}{8} $ elements, and so on. If you look into this division as binary tree, it's of height $ \lceil \log{n} \rceil $. At each level of this tree, the cost of merge is $ 2n = O(n) $. Thus, the total cost is $ \lceil \log{n} \rceil O(n) = O(n \log{n}) $.