Algorithm for MergeSort

Algorithm MergeSort(low,high)

//a[low:high] is a global array to be sorted.

//Small(P) is true if there is lnly one element

//to sort. In this case the list is already sorted

{

if(low < high) then // If there are more than one element.
{

//Divide P into subproblems.

//Find where to split the set.

mid:=[(low+high)/2];

//Solve the subproblems.

MergeSort(low,mid);

MergeSort(mid+1,high);

//Combine the solutions.

Merge(low,mid,high);

}

}





Algorithm Merge(low,mid,high)

//a[low:high] is a global array containing two sorted

//subsets in a[low:mid] and in a[mid+1:high]. The goal is to merge these two sets into

//a single set residing.

//in a[low:high]/ b[] is an auziliary global array.

{

h:=low; i:=low; j:=mid+1;

while((h<=mid) and j<=high)) do

{

if(a[h]<=a[j]) then

{

b[i]:=a[h]; h:=h+1;

}

else

{

b[i]:=a[j]; j:=j+1;

}

i:=i+1;

}



if(h>mid) then

for k:=j to high do

{

b[i]:=a[k]; i:=i+1;

}

else

for k:=h to mid do

{

b[i]:=a[k]; i:=i+1;

}

for k:=low to high do a[k]:=b[k];

}