Divide and Conquer

The main idea of divide and conquer is to split the main problem into two smaller components, assuming that each one of the components had already been solved recursively, and then try to solve the bigger problem using the solutions of the two smaller components. For example, merge sort is a perfect case of a divide and conquer problem.

In merge sort, we first divide the array given into two components, the first half and the second half. After dividing them into these two components, we then recursively apply merge sort algorithm on each of these components and assume that they are already sorted. Now the problem becomes merging two sorted arrays into one sorted array. We can use a pointer on each of these sorted arrays to solve the last part of the problem.