** Divide and Conquer**

We can make a sorting routine using merge.
* Divide and conquer* is a technique for solving
a large problem by breaking it into two smaller
problems, until the problems become easy. If we cut the problem
in half each time, the solution will be *O(log(n))* or
*O(n · log(n))*.

- If divide-and-conquer cuts the problem in half at each step,
the problem size will decrease very fast: by a factor of 1,000
in 10 steps, a factor of 1,000,000 in 20 steps, a factor of
1,000,000,000 in 30 steps.
- We soon reach a problem of size 1, which is usually easy to solve.
- Time will be
*O(log(n))*if we only process one of the halves, as in binary search. - Time will be
*O(n · log(n))*if we process both halves, as in sorting.