Divide and conquer is an algorithm 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 the Divide and conquer algorithm

  • It divides the unsorted list into N sublists until 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 until there is only one sublist remaining. This will be the sorted list

Implementation example

Share to social

Giau Ngo

Giau Ngo is a software engineer, creator of HelloKoding. He loves coding, blogging, and traveling. You can find him on Twitter, GitHub and LinkedIn