The kings and the imperial powers have from times immemorial used the “Divide and Conquer” methodology to rule over their subjects and kingdoms. A very effective method indeed if you were to consider the example of Indian history and how the British used this for consolidating their authority over the Indian subcontinent. But, did you know that this “Divide and Conquer” paradigm can also be used in developing efficient algorithms for solving quiet a few problems effectively.

One such case is the problem of sorting. Merge sort uses the divide and conquer approach for solving the sorting problem. If you were to use a simple sorting algorithm like the Insertion sort, for let’s say sorting an array of a million numbers,it would take quiet a while to arrive at the solution. The same sorting problem can be solved much faster using the Merge sort algorithm.

Now, i won’t go in to details explaining merge sort and insertion sort (already a lot of literature is available on this on the internet), but, there is something called as asymptotic notation for denoting the worst or average case running time of such algorithms. The average case running time of Insertion sort is Theta(n squared) while that of Merge sort is Theta( n * log n). This implies that for a large enough “n” merge sort will always outperform insertion sort, though for small problems insertion sort might be more suitable. These details you can find in an algorithm and data structures book like “Introduction To Algorithms” by Cormen, Leiserson, Rivest and Stein. The implementation below is based on the pseudo code given in this book.

If you are more interested you can look up how the “Divide and Conquer” approach is used for designing algorithms and also how the asymptotic notation is used in their analysis.

The below code gives an implementation of merge sort in C and also shows how for sorting a 10000 element array, the number of CPU cycles taken by insertion sort is more than merge sort.

#include <stdio.h>
#include <conio.h>
#include <time.h>
int arrayToSort[10000];
void InsertionSort(int arrayToSort[], int start, int end)
{
int i, j, key;
clock_t cstart, cfinish;
cstart = clock();
for (j = start; j <= end; j++)
{
key = arrayToSort[j];
i = j - 1;
while ( i >= 0 && arrayToSort[i] >= key)
{
arrayToSort[i+1] = arrayToSort[i];
i = i - 1;
}
arrayToSort[i+1] = key;
}
cfinish = clock();
printf("The number of CPU clock cycles for Insertion Sort is %d\n", (cfinish - cstart));
printf("Press any key to continue\n");
getchar();
printf("The result of Insertion Sort is:\n");
for ( i = start; i < end; i++)
printf("%d\t", arrayToSort[i]);
printf("\nPress any key to continue\n");
getchar();
}
void Merge(int tempArray[], int start, int mid, int end)
{
int leftArray[5001];
int rightArray[5001];
int n1 = mid - start + 1;
int n2 = end - mid;
int i, j, k;
for (i = 0; i < n1; i++)
{
leftArray[i] = tempArray[start + i];
}
for (j = 0; j < n2; j++)
{
rightArray[j] = tempArray[mid + j + 1];
}
// Assign the Sentinel value
leftArray[i] = 99999;
rightArray[j] = 99999;
i = 0;
j = 0;
for (k = start; k <= end; k++)
{
if(leftArray[i] <= rightArray[j])
{
tempArray[k] = leftArray[i];
i = i + 1;
}
else
{
tempArray[k] = rightArray[j];
j = j + 1;
}
}
}
void MergeSort(int tempArray[], int start, int end)
{
int mid;
if(start < end)
{
mid = (start + end) / 2;
MergeSort(tempArray, start, mid);
MergeSort(tempArray, (mid+1), end);
Merge(tempArray, start, mid, end);
}
}
int main(void)
{
int i;
clock_t start, finish;
// Initialize the array for the simulation of worst case in Insertion Sort
for ( i = 0; i < 10000; i++)
arrayToSort[i] = 10000 - i;
InsertionSort( arrayToSort, 0, 10000);
// Initialize the array again for the simulation of worst case in Merge Sort
for ( i = 0; i < 10000; i++)
arrayToSort[i] = 10000 - i;
start = clock();
MergeSort(arrayToSort, 0, 9999);
finish = clock();
printf("The number of CPU clock cycles for Merge Sort is %d\n", (finish-start));
printf("Press any key to continue\n");
getchar();
printf("The result of Merge Sort is:\n");
for ( i = 0; i < 10000; i++)
printf("%d\t", arrayToSort[i]);
printf("Press any key to exit\n");
getchar();
return 1;
}

On my Intel Core-i5 laptop, the number of cycles for insertion sort comes out to be 160 and for merge sort it comes out to 37.

Hope you will find this interesting enough to get started on learning algorithms and data structures.