Merging of two sorted lists

Assume that two lists to be merged are sorted in descending order. Compare the first element of the first list with the first element of the second list. If the element of the first list is greater, then place it in the resultant list. Advance the index of the first list and the index of the resultant list so that they will point to the next term. If the element of the first list is smaller, place the element of the second list in the resultant list. Advance the index of the second list and the index of the resultant list so that they will point to the next term.
 
Repeat this process until all the elements of either the first list or the second list are compared. If some elements remain to be compared in the first list or in the second list, place those elements in the resultant list and advance the corresponding index of that list and the index of the resultant list.
 
Suppose the first list is 10 20 25 50 63, and the second list is 12 16 62 68 80. The sorted lists are 63 50 25 20 10 and 80 68 62 16 12.
 
The first element of the first list is 63, which is smaller than 80, so the first element of the resultant list is 80. Now, 63 is compared with 68; again it is smaller, so the second element in the resultant list is 68. Next, 63 is compared with 50. In this case it is greater, so the third element of the resultant list is 63.
 
Repeat this process for all the elements of the first list and the second list. The resultant list is 80 68 63 62 50 25 20 16 12 10.

Example

#include<stdio.h>

int 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];
   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*/
   getchar();
   return 0;
}
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++;
   }
}

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.