Tuesday, March 29, 2016

C program to implement merge sort using recursive technique

#include<stdio.h>
#include<conio.h>
void merge_sequence(int [],int,int,int);
void merge(int arr_new[],int p, int q)
{
 int mid;
 if(p<q)
  {
   mid=(q+p)/2;
   merge(arr_new,p,mid);
   merge(arr_new,mid+1,q);
   merge_sequence(arr_new,p,mid,q);
  }
}
void merge_sequence(int arr_temp[],int l, int m,int r)
{
 int n1,n2;
 int i,j,k;
 int l_arr[100],r_arr[100];
 n1=m-l+1;
 n2=r-m;
 for(i=0;i<n1;i++)
  {
   l_arr[i]=arr_temp[l+i];
  }
 for(j=0;j<n2;j++)
  {
   r_arr[j]=arr_temp[m+j+1];
  }
 i=0;
 j=0;
 k=l;
 while(i<n1&&j<n2)
  {
   if(l_arr[i]<=r_arr[j])
    {
     arr_temp[k]=l_arr[i++];
     k=k+1;
    }
   else
    {
     arr_temp[k]=r_arr[j++];
     k=k+1;
    }
  }
 while(i<n1)
  {
   arr_temp[k]=l_arr[i++];
   k=k+1;
  }
 while(j<n2)
  {
   arr_temp[k]=r_arr[j++];
   k=k+1;
  }
}
void main()
{
 clrscr();
 int arr[10]={5,9,7,0,3,8,9,66,90,2};
 int i,j;
 printf("input array :");
 for(i=0;i<10;i++)
  {
   printf(" %d",arr[i]);
  }
 merge(arr,0,9);
 printf("\n");
printf("sorted array:");
 for(i=0;i<10;i++)
  {
   printf(" %d",arr[i]);
  }
 getch();
}

output
input array :5 9 7 0 3 8 9 66 90 2
sorted array :0 2 3 5 7 8 9 9 66 90

No comments:

Post a Comment