4
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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) Merge Sort Recursion Tree

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)$$

$\endgroup$
0
$\begingroup$

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}) $.

$\endgroup$
  • $\begingroup$ How the height is $ \lceil \log{n} \rceil $? why not just $ \log{n} $ $\endgroup$ – vivek Mar 16 '16 at 8:58
  • $\begingroup$ Actually it's $ \lceil \log{n} \rceil + 1 $. Consider any sequence with the number of elements which is not degree of 2: for instance an array of seven elements has height of four levels which is not $ \log{7} $ but $ \lceil \log{7} \rceil + 1 $. But for the matter of complexity it's not important if it's $ \lceil \log{n} \rceil $ or $ \log{n} $, it is the constant factor which does not affect the big O calculus. $\endgroup$ – karastojko Mar 16 '16 at 9:09
  • $\begingroup$ If a number is not a power of 2 say $n = 3$ then we split it as $3 \to 2,1$ and then $2 \to 1,1$. This took 2 steps which is the same as $\lceil\log 3\rceil$ $\endgroup$ – Banach Tarski Mar 16 '16 at 9:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.