Analysis of Merge Sort

Given that the merge function runs in $\Theta(n)$ time when merging $n$ elements, how do we get to showing that mergeSort() runs in $\Theta(n \log n)$ time? We start by thinking about the three parts of divide-and-conquer and how to account for their running times. We assume that we're sorting a total of $n$ elements in the entire array.

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–$\Theta$ notation, we indicate constant time by $\Theta(1)$.

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.

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

To keep things reasonably simple, let's assume that if $n \gt 1$, then $n$ is always even, so that when we need to think about $n/2$, it's an integer. (Accounting for the case in which $n$ is odd doesn't change the result in terms of big–$\Theta$ notation.) So now we can think of the running time of mergeSort() on an $n$–element subarray as being the sum of twice the running time of mergeSort() on an ($n/2$)-element subarray (for the conquer step) plus $cn$ (for the divide and combine steps—really for just the merging).

Now we have to figure out the running time of two recursive calls on $n/2$ elements. Each of these two recursive calls takes twice of the running time of mergeSort() on an ($n/4$)–element subarray (because we have to halve $n/2$) plus $cn/2$ to merge. We have two subproblems of size $n/2$, and each takes $cn/2$ time to merge, and so the total time we spend merging for subproblems of size $n/2$ is $2 . cn/2 = cn$.

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