# Merge

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

``````#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;
}``````