Monday 10 March 2014

Program In C++ for merge sort and its time complexity

#include<iostream.h>
#include<conio.h>
#include<time.h>
#include<dos.h>
#include<limits.h>
void merge(int a[],int p,int q,int r)
{int i,j;
int n1=q-p+1;
int n2=r-q;
int L[6];int R[6];
for(i=0;i<n1;i++)
  L[i]=a[p+i];
for(j=0;j<n2;j++)
  R[j]=a[q+j+1];
 L[n1]=INT_MAX;
 R[n2]=INT_MAX;
 i=0;j=0;
 for(int k=p;k<=r;k++)
 { if(L[i]<R[j])
   { a[k]=L[i];
     i++; }
   else
   { a[k]=R[j];
     j++;
   }
 }
}
void mergesort(int a[],int p,int r)
{ int q;
if(p<r)
{ q=(p+r)/2;
mergesort(a,p,q);
mergesort(a,q+1,r);
merge(a,p,q,r);
 }
}
void main()
{ clrscr();
int a[10],n,i;
clock_t start, end;
cout<<"\nEnter The Size Of Array: ";
cin>>n;
cout<<"\nEnter The Array: ";
for(i=0;i<n;i++)
cin>>a[i];
start=clock();
mergesort(a,0,n-1);
delay(200);
end=clock();
cout<<"\nArray After Sorting Is: ";
for(i=0;i<n;i++)
cout<<a[i]<<"\t";
cout<<"\nTime Taken Is: "<<(end-start)/CLK_TCK;
getch();
}

No comments:

Post a Comment