# Merge sort: sorting and merging complexity $\Theta(n)$

So this is the Master theorem for Merge Sort:

$$T(n) = 2T(n/2) + \Theta(n).$$

I am not able to understand why is the time complexity for sorting and merging $$\Theta(n)$$.

Is sorting $$O(1)$$ and merging $$O(n)$$?

• No, that is not the "Master's theorem" for merge sort; that is simply its time complexity expressed as a recursion which can be asymptotically approximated using the master theorem (no capital and no apostrophe; "master" is not someone's name). – dkaeae Feb 20 '19 at 9:50
• Also, if you mean $\Theta(n)$ (instead of $\theta(n)$), merging takes worst-case linear steps since, in the worst-case, you merge 2 lists of (approximately) $\frac{n}{2}$ elements each. – dkaeae Feb 20 '19 at 9:51

Each iteration of merge sort consist of 2 phases:

1. Merge Sorting the first and the second half separately.
2. Merging the two halves.

So in your equation phase 1 is represented by $$2T(n/2)$$. This means that merge sort is called on the two halves. This is a recursive call, which is why $$T$$ is used here.

Phase 2 is represented by $$\Theta(n)$$. Merging two lists of length $$a$$ and length $$b$$ takes $$\Theta(a+b)$$. In our case the two lists are both of size $$\frac{1}{2}n$$, so we get a total of $$\Theta(n)$$.

In the end we get that $$T(n) =$$ step 1 + step 2, resulting in $$T(n) = 2T(n/2) + \Theta(n)$$