What is it
Divide and Conquer is an algorithm design paradigm. It works by breaking the original problem into similar subproblems recursively. The solutions to subproblems are then combined to give the solution to the original problem. (Wikipedia)
Following that intuition, there are three steps in each recursion calls:
- Divide: Divide the problem into subproblems.
- Conquer: If the sizes of subproblems are small enough, solve them directly; or, solve them recursively.
- Combine: Combine solutions from subproblems for the original problem.
How to use it
That’s it! Simple, right? Let’s walk through it in details with an example – Mergesort.
Remember that there are three steps in divide and conquer, what shall we do specifically here? Given the input
- Divide: Divide the original array into subarrays.
- Conquer: If there is only one item left, return it directly as it’s already been sorted; else, recursively divide the subarray into sub-subarrays.
- Combine: Combine two sorted subarrays into a sorted array.