Determine the complexity of following sorting algorithms > Merge Sort

We assume that we're sorting a total of $n$ elements in the entire array.

1. The divide step takes constant time, regardless of the subarray size. After all, the divide step just computes the midpoint $q$ of the indices $p$ and $r$. Recall that in big-Θ notation, we indicate constant time by $\Theta(1)$.
2. The conquer step, where we recursively sort two subarrays of approximately $n/2$ elements each, takes some amount of time, but we'll account for that time when we consider the subproblems.
3. The combine step merges a total of $n$ elements, taking $\Theta(n)$ time.

If we think about the divide and combine steps together, the $\Theta(1)$ running time for the divide step is a low-order term when compared with the $\Theta(n)$running time of the combine step. So let's think of the divide and combine steps together as taking $\Theta(n)$ time. To make things more concrete, let's say that the divide and combine steps together take $cn$ time for some constant $c$.

Let's draw out the merging times in a "tree":

Computer scientists draw trees upside-down from how actual trees grow. Atree is a graph with no cycles (paths that start and end at the same place). Convention is to call the vertices in a tree its nodes. The root node is on top; here, the root is labeled with the $n$ subarray size for the original $n$-element array. Below the root are two child nodes, each labeled $n/2$ to represent the subarray sizes for the two subproblems of size $n/2$.

What do you think would happen for the subproblems of size $n/8$? There will be eight of them, and the merging time for each will be $cn/8$, for a total merging time of $8 \cdot cn/8 = cn$:

As the subproblems get smaller, the number of subproblems doubles at each "level" of the recursion, but the merging time halves. The doubling and halving cancel each other out, and so the total merging time is $cn$ at each level of recursion. Eventually, we get down to subproblems of size 1: the base case. We have to spend $\Theta(1)$ time to sort subarrays of size 1, because we have to test whether $p < r$, and this test takes time. How many subarrays of size 1 are there? Since we started with $n$ elements, there must be $n$ of them. Since each base case takes $\Theta(1)$ time, let's say that altogether, the base cases take $cn$time:

When we use big-Θ notation to describe this running time, we can discard the low-order term ($+1$) and the constant coefficient ($c$), giving us a running time of $\Theta(n \lg n)$, as promised.

Read more from Source: https://www.khanacademy.org/computing/computer-science/algorithms/merge-sort/a/analysis-of-merge-sort