Merge Sort - for my students...

Using divide-and-conquer policy we can solve a sorting problem. The divide-and-conquer method suggests the sorting algorithm with the following structure.: if n is one, terminate; otherwise partition the collection of elements into two or more sub collections.; sort each; combine the sub collections into a single sorted collection.

It can be depicted as follows:

void Sort(a[], n)

{

    if(n>= k) { //k is global

        i = n/k;

        j = n-i;

    Let A consist of the first i elements in a[]

    Let B consists of the remaining j elements in E

    Sort(A,i);

    Sort(B,j);

    merge(A,B,a,i,j); //merge A and B into a[]

}

 else sort a[] using insertion sort.

}

In the above pseudo code, if we make k = 2, we get merge sort.

The complete source code of Merge Sort can be found here.

Analysis of Merge Sort:

From the following algorithm of Merge Sort, the run time T(n) can be deduced as follows:

void MergeSort(int a[], int low, int high)

{

int mid;

if(low(high))

{

mid = (low+high)/2; ==> Θ(1)

MergeSort(a,low,mid); ==>T(n/2)

MergeSort(a,mid+1,high);==>T(n/2)

merge(a,low,mid,high);==>Θ(n)

}

}

Therefore we can write T(n) = 2T(n/2) + Θ(n)

Comparing it with the Master theorem, we get a = 2, b  = 2 and d = 1. Hence a = b^d which means it is the second condition of the Master Theorem.

Thus we get T(n) = Θ (n log n)