The divide-and-conquer paradigm involves three steps at each level of the recursion:

  • Dividethe problem into a number of subproblems.
  • Conquerthe subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner.
  • Combinethe solutions to the subproblems into the solution for the original problem.