Mergesort

The following is the algorithm of mergesort

1)split the array into two almost equal halves(subarray 1 ,subarray 2)
2)sort the subarray 1
3)sort the subarray 2
4)merge the sorted sub arrays
5)follow steps 1 to 4 recursively for sorting the sub arrays till array size is 1.

algorithm for merging
1)set counters i and j to the beginning of sub arrays 1 and 2
2)compare the elements referred by i and j and copy the smaller element to a temporary array and increment the respective counter.
3)repeat step 2 till elements of subarray 1 or subarray 2 are exhausted.
4)copy the remaining elements of the array that is not exhausted to the temporary array in the same order.
5)copy the content of temporary array back to original array.


The following program implements mergesort

#include
using namespace std;

void mergesort(int *,int,int);
void merge(int*,int,int,int);
int b[100];

int main()
{
   int a[100],i,n;
   cout << "Enter the number of terms";
   cin>>n;
   cout<<"Enter elements";
   for(i=0;i   {
       cout<<"Enter the element in position "<       cin>>a[i];
    }
    mergesort(a,0,n-1);
    cout<<"After mergesort";
    for(i=0;i   {
       cout<    }
   return 0;
}

void mergesort(int a[],int i,int j)
{
    int mid;
    if(i    {
        mid = (i+j)/2;
        mergesort(a,i,mid);
        mergesort(a,mid+1,j);
        merge(a,i,mid,j);
    }
}

void merge(int a[],int low,int mid,int high)
{
    int h,i,j,k;
    h=low;
    i=low;
    j=mid+1;
    while(h<=mid && j<= high)
    {
        if(a[h] <= a[j])
        b[i]=a[h++];
        else
        b[i]=a[j++];
        i++;
     }
    if(h>mid)
    {
        for(k=j;k<=high;k++)
        b[i++]=a[k];
';
    }
    else
    {
       for(k=h;k<=mid;k++)
        b[i++]=a[k];
     
    }
    for(k=low;k<=high;k++)
    {
        a[k]=b[k];
    }
}