Divide and conquer is "an algorithm design paradigm that is based on multi-branch recursion. It takes a larger problem and breaks it into 2+ sub-problems" (Wikipedia). Merge sorting and some fibonacci algorithms are implementations of the divide and conquer algorithm. These are especially useful on multi-processor systems. Quicksort algorithms also employ the divide-and-conquer algorithmic paradigm.
Divide-and-conquer algorithms have three parts:
- Divide the problem into a number of subproblems that are smaller instances of the same problem.
- Conquer the subproblems by solving them recursively. If they are small enough, solve the subproblems as base cases.
- Combine the solutions to the subproblems into the solution for the original problem.
