Program for Merging of Two Sorted Lists with Example & Explanation

Program

#include<stdio.h>
#include<conio.h>
void main()
{
   void read(int *,int);
   void dis(int *,int);
   void sort(int *,int);
   void merge(int *,int *,int *,int);
   int a[5],b[5],c[10];
   clrscr();
   printf("Enter the elements of first list \n");
   read(a,5);      /*read the list*/
   printf("The elements of first list are \n");
   dis(a,5);  /*Display the first list*/
   printf("Enter the elements of second list \n");
   read(b,5);   /*read the list*/
   printf("The elements of second list are \n");
   dis(b,5);  /*Display the second list*/
   sort(a,5);
   printf("The sorted list a is:\n");
   dis(a,5);
   sort(b,5);
   printf("The sorted list b is:\n");
   dis(b,5);

   merge(a,b,c,5);
   printf("The elements of merged list are \n");
   dis(c,10);  /*Display the merged list*/
   getch();
}
void read(int c[],int i)
{
   int j;
   for(j=0;j<i;j++)
      scanf("%d",&c[j]);
   fflush(stdin);
}

void dis(int d[],int i)
{
   int j;
   for(j=0;j<i;j++)
      printf("%d ",d[j]);
   printf("\n");
}
void sort(int arr[] ,int k)
{
   int temp;
   int i,j;
   for(i=0;i<k;i++)
   {
      for(j=0;j<k-i-1;j++)
      {
         if(arr[j]<arr[j+1])
         {
            temp=arr[j];
            arr[j]=arr[j+1];
            arr[j+1]=temp;
         }
      }
   }
}
void merge(int a[],int b[],int c[],int k)
{
   int ptra=0,ptrb=0,ptrc=0;
   while(ptra<k && ptrb<k)
   {
      if(a[ptra] < b[ptrb])
      {
            c[ptrc]=a[ptra];
         ptra++;
      }
      else
      {
            c[ptrc]=b[ptrb];
         ptrb++;
      }
      ptrc++;
   }
   while(ptra<k)
   {
      c[ptrc]=a[ptra];
      ptra++;ptrc++;
   }
   while(ptrb<k)
   {
      c[ptrc]=b[ptrb];
      ptrb++;  ptrc++;
   }
}

Example

Input

Enter the elements of the first list

10 20 25 50 63

Output

The elements of first list are

20 25 50 63

Input

Enter the elements of the second list

16 62 68 80

Output

The elements of second list are

12 16 62 68 80

The sorted list a is

63 50 25 20 10

The sorted list b is

80 68 62 16 12

The elements of the merged list are

80 68 63 62 50 25 20 16 12 10

Explanation

1. ptra=0, ptrb=0, ptrc=0;
2. If the element in the first list pointed to by ptra is greater than the element in the second list pointed to by ptrb, place the element of the first list in the resultant list at the index equal to ptrc. Increment ptra or ptrc by one, or else place the element of the second list in the resultant list at the index equal to ptrc. Increment ptrb and ptrc by 1. Repeat this step until ptra is greater than the number of terms in the first list and ptrb is greater than the number of terms in the second list.
3. If the first list has any elements, place one in the resultant list pointed to by ptrc, and increment ptra and ptrc. Repeat this step until ptra is greater than the number of terms in the first list.
4. If the second list has any elements, place one in the resultant list pointed to by ptrc, and increment ptrb and ptrc. Repeat this step until ptrb is greater than the number of terms in the first list.