Data Structures and Algorithms - Old Questions

7. Explain Divide and Conquer algorithm taking reference to Merge Sort.

Divide-and-conquer algorithm breaks a problem into subproblems that are similar to the original problem, recursively solves the subproblems, and finally combines the solutions to the subproblems to solve the original problem.

Divide and Conquer algorithm consists of the following three steps.

1. Divide: Divide the original problem into a set of subproblems.
2. Conquer: Solve every subproblem individually, recursively.
3. Combine: Put together the solutions of the subproblems to get the solution to the whole problem.

Merge sort works on the basis of divide and conquer algorithm. The basic concept of merge sort is divides the list into two smaller sub-lists of approximately equal size. Recursively repeat this procedure till only one element is left in the sub-list. After this, various sorted sub-lists are merged to form sorted parent list. This process goes on recursively till the original sorted list arrived.

Procedure for Merge sort:

To sort A[l…………r]

1.      Divide step: If a given array A has zero or one element, simply return; it is already sorted. Otherwise split A[l……….r] into two sub-arrays A[l………q] and A[q+1…………r] each containing about half of the element A[l…….r]. that is q is the half of way point of A[l…….r].

2.      Conquer step: Sorting the two sub-arrays A[l………q] and A[q+1…………r] recursively. When the size of sequence of is 1 there is nothing more to do.

3.      Combine step: Combine the two sub-arrays A[l……q] and A[q+1…………r] into a sorted sequence.