Introduction

Summary

We can use divide-and-conquer methods to break up a large problem into many smaller problems, which are easier to tackle than the big problem. We then look to combine the solutions to the smaller problems in some manner to solve the initial problem.

Philosophy

To solve a problem of size $n$:

• Divide the problem into subproblems, each of size $\lt 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.

The Question We Ask Ourselves

When we look to use divide-and-conquer to solve a given problem, we must ask ourselves:

• How do we divide the problem into many subproblems?
• How do we combine/merge the subsolutions to get the whole solution?

Merge Sort

How it Works

Animation of merge sort algorithm, used to sort numbers.

To sort $n$ numbers:

$$ \begin{array}{lcl} \text{if $n \le 1$} &: &\text{do nothing.} \\ \text{if $n \ge 2$} &: &\text{divide the $n$ numbers arbitrarily into two sequences,} \\ & &\text{both of size $n/2$, run Merge Sort twice, once for each sequence.} \\ \\ & &\text{Then, merge the two sorted sequences into one sorted sequence.} \end{array} $$

Time Complexity Analysis

Let there be a constant $c > 0$ such that