Divide and Conquer

Divide and Conquer

Using Divide-and-Conquer, a problem is solved recursively, applying three steps at each level of the recursion:

Divide the problem into a number of sub problems that are smaller instances of the same problem.

Conquer the sub problems by solving them recursively. If the sub problem sizes are small enough,   however, just solve the sub problems in a straightforward manner (base case).

Combine the solutions to the sub problems into the solution for the original problem.

In divide and conquer approach, the problem in hand, is divided into smaller sub-problems and then each problem is solved independently. When we keep on dividing the sub problems into even smaller sub-problems, we may eventually reach a stage where no more division is possible. Those "atomic" smallest possible sub-problems (fractions) are solved. The solution of all sub-problems is finally merged in order to obtain the solution of an original problem.

Following are some standard algorithms that are Divide and Conquer algorithms.

Binary search, Quick sort, Merge Sort.

Example: Merge Sort

Above picture is about Merge sort, where a list is divided until list becomes atomic. Then elements are sorted and sub lists are formed. this process goes on until list gets sorted.