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