i. Implement Insertion Sort (The program should report the number of comparisons) ii. Implement Merge Sort(The program should report the number of comparisons)

---

#include<iostream.h>
#include<conio.h>
void mergesort(int[],int,int);
void merge(int[],int,int,int);
void insert(int[],int);
void display(int[],int);
int pp=0;
void main()
{
clrscr();
int i,j,n,m,a[10];
cout<<"enter the size "<<endl;
cin>>n;
cout<<"enter the numbers "<<endl;
for(i=0;i<n;i++)
{
cin>>a[i];
}
cout<<"enter option"<<endl;
cout<<"1.insertion sort"<<endl;
cout<<"2.merge sort"<<endl;
cin>>m;
if(m==1)
{
cout<<"Using insertion sort :";
insert(a,n);
display(a,n);
}
else
{

cout<<"Using merge sort :";
mergesort(a,0,n-1);
for(i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<"No of Comparision :"<<pp;
}
getch();
}
void insert(int a[10],int n)
{
int i,j,temp,count=0,cn1=0;
for(j=1;j<n;j++)
{
temp=a[j];
i=j-1;
while(i>=0&&a[i]>temp)
{
count++;
a[i+1]=a[i];
i=i-1;
}
{
a[i+1]=temp;
if(count==0)
{
cn1++;
}
}
}
cout<<"No of Comparision for insertion sort :"<<count+cn1<<endl;

}
void display(int a[10],int n)
{
cout<<"sorted array is : ";
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ,";
}
}
void mergesort(int a[20],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 merge(int a[10],int p,int q,int r)
{
int i,j,k;
int n1=q-p+1;
int n2=r-q;
int l[20],rr[20];
for(i=0;i<n1;i++)
l[i]=a[p+i];
for(j=0;j<n2;j++)
rr[j]=a[q+j+1];
i=0;
j=0;
k=p;
while(i<n1&&j<n2)
{
if(l[i]<=rr[j])
{
a[k]=l[i];
i++;
pp++;
}
else
{
a[k]=rr[j];
j++;
pp++;
}
k++;
}
while(i<n1)
{       pp++;
a[k]=l[i];
i++;
k++;
}
while(j<n2)
{
pp++;
a[k]=rr[j];
j++;
k++;
}
}

---

Output:-