Tuesday, September 28, 2010

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 = bd which means it is the second condition of the Master Theorem.

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

No comments:

Share