Merge Sort

#include<stdio.h>

void merge(int a[],int beg,int mid,int end)
{
    int i=beg,j=mid+1,index=beg,temp[50],k;
    while((i<=mid)&&(j<=end))
    {
        if(a[i]<a[j])
        {
            temp[index]=a[i];
            i++;
        }
        else
        {
            temp[index]=a[j];
            j++;
        }
        index++;
    }
    if(i>mid)
    {
        while(j<=end)
        {
            temp[index]=a[j];
            j++;
            index++;
        }
    }
    else
    {
        while(i<=mid)
        {
            temp[index]=a[i];
            i++;
            index++;
        }
    }
    for(k=beg;k<index;k++)
        a[k]=temp[k];
}

void merge_sort(int a[],int beg,int end)
{
    int mid;
    if(beg<end)
    {
        mid=(beg+end)/2;
        merge_sort(a,beg,mid);
        merge_sort(a,mid+1,end);
        merge(a,beg,mid,end);
    }
}

void main()
{
 int a[50],i,n;
 printf("Enter no. of elements ");
 scanf("%d",&n);
 printf("Enter numbers ");
 for(i=0;i<n;i++)
    scanf("%d",&a[i]);
 merge_sort(a,0,n-1);
 printf("Sorted array is ");
 for(i=0;i<n;i++)
    printf("%d ",a[i]);
}

/*Output
Enter no. of elements 5
Enter numbers 98 65 31 22 11
Sorted array is 11 22 31 65 98
*/

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s