program for merge sorting in Data structure With Example

Program

#include <stdio.h>
#define MAX 10
void merge(int list[],int list1[],int k,int m,int n)
{
    int i,j;
   i=k;
   j = m+1;
   while( i <= m && j <= n)
   {
      if(list[i] <= list[j])
      {
             list1[k] = list[i];
         i++;
         k++;
      }
      else
      {
            list1[k] = list[j];
         j++;
         k++;
      }
   }
   while(i <= m)
   {
         list1[k] = list[i];
      i++;
      k++;
   }
   while (i <= n )
   {
         list1[k] = list[j];
      j++;
      k++;
   }
}

void mpass( int list[],int list1[],int l,int n)
{
   int i;
   i = 0;
   while( i <= (n-2*l+1))
   {
      merge(list,list1,i,(i+l-1),(i+2*l-1));
      i = i + 2*l;
   }
   if((i+l-1) < n)
       merge(list,list1,i,(i+l-1),n);
   else
       while (i <= n )
       {
              list1[i] = list[i];
              i++;
       }
   }
   void msort(int list[], int n )
   {
      int l;
      int list1[MAX];
      l =1;
      while (l <= n )
      {
         mpass(list,list1,l,n);
         l = l*2;
         mpass(list1,list,l,n);
         l = l*2;
      }
   }

   void readlist(int list[],int n)
   {
      int i;
      printf("Enter the elements\n");
      for(i=0;i<n;i++)
          scanf("%d",&list[i]);
   }

   void printlist(int list[],int n)
   {
      int i;
      printf("The elements of the list are: \n");
      for(i=0;i<n;i++)
          printf("%d\t",list[i]);
   }

void main()
{
   int list[MAX], n;
   printf("Enter the number of elements in the list max = 10\n");
   scanf("%d",&n);
   readlist(list,n);
   printf("The list before sorting is:\n");
   printlist(list,n);
   msort(list,n-1);
   printf("The list after sorting is:\n");
   printlist(list,n);
}

Example

Input

Enter the number of elements in the list, max = 10

10

Enter the elements

11
2
45
67
33
22
11
0
34
23

Output

The list before sorting has the following elements:

11 2 45 67 33 22 11 0 34 23

The list after sorting has the following elements:

0 2 11 11 22 23 33 34 45 67

Explanation

1. The merging of two sublists, the first running from the index 0 to m, and the second running from the index (m + 1) to (n − 1) requires no more than (n−l + 1) iterations.
2. So if l =1, then no more than n iterations are required, where n is the size of the list to be sorted.
3. Therefore, if n is the size of the list to be sorted, every pass that a merge routine performs requires a time proportional to O(n), since the number of passes required to be performed is log2n.
4. The time complexity of the algorithm is O(n log₂(n)), for both average-case and worst-case. The merge sort requires an additional list of size n.