Divide and Conquer is a method for solving a problem by the following steps

  • Divide recursively the problem into non overlapping subproblems until these become simple enough to be solved directly
  • Conquer the subproblems by solving them recursively. If they are small enough, solve them as base cases
  • Combine the solution to the subproblems into the solution for the original problem

Let's see a specific example

Merge Sort

Merge sort is an efficient sorting algorithm using Divide and Conquer method.

  • It divide the unsorted list into N sublists util each containing one element
  • Sort/Conquer the sublists by solving them as base cases, a list of one element is considered sorted
  • Repeatedly merge/combine sublists to produce new sorted sublists util there is only one sublist remaining. This will be the sorted list

Implementation example