One of the most basic and powerful algorithmic techniques is Divide and Conquer. For example, the binary search algorithm, which I’ll describe in the context of guess a number game between 1 and 100. Suppose someone picks a number between 1 and 100, and allows you to ask questions of the form “Is the number greater than k?” where k is an integer you choose. In this problem, goal is to ask as few questions as possible to figure out the number. Your first question should be “Is the number greater than 50?” Why? Because after asking if the number is bigger than 50, you have learned either that the number is between 1 and 50, or that the number is between 51 and 100. In either case have reduced your problem to one in which the range is only half as big. Thus you have divided the problem up into a problem that is only half as big, and you can now (recursively) conquering this remaining problem.

Merge sort algorithm also uses this divide and conquer strategy to sort an array of elements. Merge sort algorithm performs sorting in two phases. In first phase, algorithm splits an array into two equal length sub-arrays. This process recursively continues on the sub-arrays until there is only one element in the sub-array. In phase two, merging process takes place that will take two sorted sub-arrays of A and merges them into a single sorted sub-array of A.

MergeSort(A, left, right) {

if (left < right) {

mid = floor((left + right) / 2);

MergeSort(A, left, mid);

MergeSort(A, mid+1, right);

Merge(A, left, mid, right);



Merge(A, left, mid, right) {

int B[left..right]; int i=k=left; int j = mid+1

while (i <= mid) and (j <= right)

if (A[i] <= A[j])

B[k++] = A[i++];


B[k++] = A[j++];

while (i <= mid)

B[k++] = A[i++];

while (j <= right)

B[k++] = A[j++];

for (i = left; i <= right; i++)

A[i] = B[i];


Graphical Explanation

Consider the following array: A = {7, 5, 2, 4, 1, 6, 3, 0};

In first phase, algorithm will split this array into single element sub-arrays.

In second phase, algorithm will combine two sorted sub-arrays in to a single sorted sub-array. Finally, a single sorted array remains that contain the sorted output.


Tagged with: C/C++ language

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>


Looking for something?

Use the form below to search the site:

Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Related News Feeds

Set your Twitter account name in your settings to use the TwitterBar Section.