The heart of merge sort is the merge procedure. Once you understand the merge procedure, understanding merge sort becomes very simple. You can click the links below…

**Prerequisite for this lesson**

- Understanding Merge Procedure With Time Complexity Analysis
- C Program for Merge Sort

**Analysis of time complexity of merge sort (Method 1)**:

The merge sort is a divide and conquer algorithm, which means that the input array of size n is divided into two parts each of size n/2. The array of size n/2 is further divided into two parts each of size n/4. This process continues until an array of 1 element is obtained which can no longer be divided.

As you can see in the figure above,

**Level 0**: 1 array of size *n*
**Level 1**: 2 arrays each of size *n/2*
**Level 2**: 4 arrays each of size *n/4*
- . . .
- . . .
**Level ***i-2*: *n/4* arrays each of size 4
**Level ***i-1*: *n/2* arrays each of size 2
**Level ***i*: *n* arrays each of size 1

In each level, the work down is *c*n* where *c* is some constant. Now the question is, how many levels will be there? Observe that size of a single array in each level is of the form:

$$\frac{n}{2^{i}}$$

where *i* is the level under consideration.

We do not know the value of last level, **i**. But we know that the size of a single array in the last level is 1. Therefore we can say that:

$$\frac{n}{2^{i}} = 1$$

or

$$n = 2^{i}$$

or

$$i = \log_{2}n$$

Hence we conclude that there are a total of *log n* levels and in each level the work done is *c*n*.

So the asymptotic time complexity of merge sort will be:

$$O(c*n*log_{2}n) = O(n*log_{2}n)$$

**Analysis of time complexity of merge sort (Method 2)**:

Another method of deriving out the time complexity is by using the recurrence equation. In merge sort, merge procedure takes O(n) time and by now we already know that merge sort divided a bigger problem (array of size n) into two smaller problem of equal sizes (i.e two sub array of size n/2 each.). Thus the recurrence for merge sort will be:

$$T(n) = 2T(\frac{n}{2}) + \Theta(n)$$

where T(n) is the time taken for the array of size n, T(n/2) is the time taken for sub array of size n/2. This is combined with the time complexity of merge procedure.

On solving the recurrence above using *Masters Theorem*, we will get the time complexity of merge sot as

$$O(n*log_{2}n)$$

\[\]

*Related*