#include<stdio.h>
#include<conio.h>
void mergesort(int no[],int temp[],int ar);
void m_sort(int no[],int temp[],int left,int right);
void merge(int no[],int temp[],int left,int mid,int right);
int no[10],c=0;
int temp[100];
void main()
{
int i;
clrscr();
printf("enter the 10 value for sorting");
for(i=0;i<10;i++)
scanf("%d",&no[i]);
mergesort(no,temp,10);
printf("after sorting");
for(i=0;i<10;i++)
printf("\t%d",no[i]);
printf("\nthe complexity of merge sort is=%d",c);
getch();
}
void mergesort(int no[10],int temp[10],int ar)
{
m_sort(no,temp,0,ar-1);
}
void m_sort(int no[10],int temp[10],int left,int right)
{
int mid=0;
if(right>left)
{
mid=(right+left)/2;
m_sort(no,temp,left,mid);
m_sort(no,temp,mid+1,right);
merge(no,temp,left,mid+1,right);
}
}
void merge(int no[10],int temp[10],int left,int mid,int right)
{
int i,left_end,nelement,temp_pos;
left_end=mid-1;
nelement=(right-left+1);
while((left<=left_end)&&(mid<=right))
{
c++;
if(no[left]<=no[mid])
{
temp[temp_pos]=no[left];
temp_pos++;
left++;
}
else
{
temp[temp_pos]=no[mid];
temp_pos++;
mid++;
}
}
while(left<=left_end)
{
c++;
temp[temp_pos]=no[left];
temp_pos++;
left++;
}
while(mid<=right)
{
c++;
temp[temp_pos]=no[mid];
mid++;
temp_pos++;
}
for(i=0;i<=nelement;i++)
{
no[right]=temp[right];
right--;
}
}