Saturday, 9 August 2014

Merge Sort

The following is the implementation of Merge Sort in terms of a C program. If you have any doubts or corrections, please let me know.

#include<stdio.h>
void mergesort(int x[20],int n)
  {
     int temp[20],i,j,k,l1,l2,size,u1,u2,a;
     size=1;
     while(size<n)
        {
           l1=0;
           k=0;
           while(l1+size<n)
             {
               l2=l1+size;
               u1=l2-1;
               u2=((l2+size-1<n)?l2+size-1:n-1);
               for(i=l1,j=l2;i<=u1&&j<=u2;k++)
                  {
                    if(x[i]<=x[j])
                      {
                         temp[k]=x[i];
                         i++;
                      }
                    else
                      {
                         temp[k]=x[j];
                         j++;
                      }
                   }
               for(;i<=u1;k++)
                   {
                      temp[k]=x[i];
                      i++;
                   }
               for(;j<=u2;k++)
                   {
                      temp[k]=x[j];
                      j++;
                   }
                l1=u2+1;
             }
      for(i=l1;k<n;k++)
        temp[k++]=x[i];
      for(i=0;i<n;i++)
         x[i]=temp[i];
      size=size*2;
      for(a=0;a<n;a++)
          printf(" %d  ",x[a]);
       printf("\n");
   }
}
main()
  {
    int x[20],n,i;
    printf("\nEnter the size:");
    scanf("%d",&n);
    printf("\nEnter the values");
    for(i=0;i<n;i++)
      scanf("%d",&x[i]);
    mergesort(x,n);

   }

No comments:

Post a Comment