Saturday, 31 March 2012

Program - Recursive Merge sort


Program - Recursive Merge sort 


// Merge Sort

#include<stdio.h>
#include<conio.h>

void merge_sort(int,int,int);
void msort(int,int);
int a[50],n,p=0;

void main()
{
        int i;
        clrscr();

        printf("\n How many Elements You Wnat To Enter ? : ");
        scanf("%d",&n);

        for(i=0;i<n;i++)
        {
                printf("\n Enter a[%d] : ",i);
                scanf("%d",&a[i]);
        }

        msort(0,n-1);
        printf("\n\nSorted list is : \n");
        for(i=0;i<n;i++)
        {
                printf("\n   %d",a[i]);
        }
        getch();
}


void merge_sort(int low,int mid,int high)
{
        int i,j,k,t[50];
        printf("\n Low : %d mid: %d High : %d",low,mid,high);

        i=low;
        j=mid+1;
        k=low;

        while(i<=mid && j<=high)
        {
                if(a[i]>=a[j])
                {
                        t[k++]=a[j++];
                }
                else
                {
                        t[k++]=a[i++];
                }
        }

        while(i<=mid)
        {
                t[k++]=a[i++];

        }

        while(j<=high)
        {
                t[k++]=a[j++];
        }
        for(i=low;i<=high;i++)
        {
                a[i]=t[i];
        }

        printf("\n\nArray After Pass %d is : ",++p);
        for(i=0;i<n;i++)
        {
                printf("   %d",a[i]);
        }
}

void msort(int low,int high)
{
        int mid;
        if(low!=high)
        {
                mid=(low+high)/2;
                msort(low,mid);
                msort(mid+1,high);
                merge_sort(low,mid,high);
        }
}

Posted By  :Ruchita Pandya 

No comments:

Post a Comment