QUESTION

There are two sorted arrays. First one is of size m+n containing only m elements. Another one is of size n and contains n elements. Merge these two arrays into the first array of size m+n such that the output is sorted.\n\nInput:\nThe first line contains the size of m+n array.\nThe second line contains elements of m+n array.The elements with \”-1\” denotes the vacant spaces to be filled.\nThe third line contains size of n array.\nThe fourth line contains the size of the n array.\n\nOutput:\nOutput contains m+n arrays in sorted order.

“TESTCASE_1”: “5\n4 5 -1 -1 7\n2\n8 10\n###—###SEPERATOR—###—\n4 5 7 8 10”, “TESTCASE_2”: “6\n7 -1 -1 10 -1 -1\n4\n9 8 13 12\n###—###SEPERATOR—###—\n7 8 9 10 12 13”, “TESTCASE_3”: “4\n1 -1 -1 9\n2\n80 98 \n###—###SEPERATOR—###—\n1 9 80 98”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

#include <stdio.h>

/* Assuming -1 is filled for the places where element
   is not available */


/* Function to move m elements at the end of array mPlusN[] */
void moveToEnd(int mPlusN[], int size)
{
  int i = 0, j = size - 1;
  for (i = size-1; i >= 0; i--)
    if (mPlusN[i] != -1)
    {
      mPlusN[j] = mPlusN[i];
      j--;
    }
}

/* Merges array N[] of size n into array mPlusN[]
   of size m+n*/
int merge(int mPlusN[], int N[], int m, int n)
{
  int i = n;  /* Current index of i/p part of mPlusN[]*/
  int j = 0; /* Current index of N[]*/
  int k = 0; /* Current index of of output mPlusN[]*/
  while (k < (m+n))
  {
    /* Take an element from mPlusN[] if
       a) value of the picked element is smaller and we have
          not reached end of it
       b) We have reached end of N[] */
    if ((i < (m+n) && mPlusN[i] <= N[j]) || (j == n))
    {
      mPlusN[k] = mPlusN[i];
      k++;
      i++;
    }
    else  // Otherwise take element from N[]
    {
      mPlusN[k] = N[j];
      k++;
      j++;
    }
  }
}

/* Utility that prints out an array on a line */
void printArray(int arr[], int size)
{
  int i,temp,j;
 
  for(i=0;i<size;i++)
  {
    for(j=i+1;j<size;j++)
    {
      if(arr[i]>arr[j])
      {
        temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
      }
    }
  }
 for (i=0; i < size; i++)
    printf("%d ", arr[i]);
  printf("\n");
}

/* Driver function to test above functions */
int main()
{
  /* Initialize arrays */
 int mp,i,n1,n,m;
  scanf("%d",&mp);
  int mPlusN[mp];
  for(i=0;i<mp;i++)
    scanf("%d",&mPlusN[i]);
  scanf("%d",&n1);
  int N[n1];
  for(i=0;i<n1;i++)
    scanf("%d",&N[i]);
  n = sizeof(N)/sizeof(N[0]);
  m = sizeof(mPlusN)/sizeof(mPlusN[0]) - n;

  /*Move the m elements at the end of mPlusN*/
  moveToEnd(mPlusN, m+n);

  /*Merge N[] into mPlusN[] */
  merge(mPlusN, N, m, n);

  /* Print the resultant mPlusN */
  printArray(mPlusN, m+n);
  

  return 0;
}