Data structure

Divide and Conquer Algorithm

Divide and Conquer Algorithm

In the Divide and Conquer algorithm, the problem is divided into two parts. The first part is to divide the problem into subproblems and the second part is used to solve the smaller problem and combine the final result. Divide and conquer is divided into 3 parts;

  1. Divide: Divide the problem into smaller sub-problems.
  2. Conquer: Solve sub-problems by calling recursively until solved and reached at the stage where condition is not fulfilled.
  3. Combine: Combine the sub-problems to get the final solution

Example. Merge sort, Quicksort.

Algorithm of Merge sort:

MergeSort(arr[], l,  r)

If r > l

  1. Find the middle point to divide the array into two halves:  

             middle m = l+ (r-l)/2

  1. Call mergeSort for first half:   

             Call mergeSort(arr, l, m)

  1. Call mergeSort for second half:

             Call mergeSort(arr, m+1, r)

  1. Merge the two halves sorted in steps 2 and 3:

             Call merge(arr, l, m, r)

Explanation: In the above algorithm of merge sort, the array is divided into two parts which is the first process of Divide and Conquer. And after that, both parts will divide into many subparts and solve the subproblems and combine all the subproblems to solve the actual problem.