To solve a problem of size $n$:

• Divide: the problem into subproblems, each of size < $n$:
• Conquer: Solve each subproblem recursively (and independently of the other subproblems).
• Combine/Merge the solutions to the subproblems into a solution to the original problem.

Merge Sort

To sort $n$ numbers:

• If $n \leq 1$: do nothing.
• If $n \geq 2$: divide the $n$ numbers arbitrarily into two sequences, both of size $n/2$, run Merge sort twice, once for each sequence. Then merge the two sorted sequences into one sorted sequence.

In general, if we do not assume anything about the value of $c$, we find $T(n) \leq 2c n \log_2 n$

So the running time of Merge Sort is $T(n) = O(n\log_2 n)$ if $n$ is a power of two.