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

```
```