## Given two sorted arrays, one array with size m+n and the other array with size n. We will merge the n sized array into m+n sized array and print the m+n sized merged array.

### Example :

**Input :** M[] = {1, 7, absent, absent, 124, 132, absent, 155, 200};

N[] = {2,4,152};

**Output :** {1, 2, 4, 7, 124, 132, 152, 155, 200}

## Algorithm

Let the arrays be M[] and N[]. Size of M[] be m+n and Size of N[] be n

1. First, move the non absent elements in M[] to the end and return the number of elements that are absent ie, store it in j

2. Start from the jth element of the array M[] and 0th element of the array N[] and compare each value of the two arrays, and store the elements in M[] in ascending order

**Time Complexity **

O(m+n), where m and n are sizes of the arrays .

v\:* {behavior:url(#default#VML);}

o\:* {behavior:url(#default#VML);}

w\:* {behavior:url(#default#VML);}

.shape {behavior:url(#default#VML);}

## C++ Program

```
#include <bits/stdc++.h>
#define absent INT_MAX
using namespace std;
int transform(int M[],int n)
{
int j = n-1;
for(int i=n-1;i>=0;i--)
{
if(M[i] != absent)
{
M[j]=M[i];
j--;
}
}
return (j+1); //jth index implies (j+1) elements absent
}
int main()
{
int M[] = {1, 7, absent, absent, 124, 132, absent, 155, 200};
int N[] = {2,4,152,360};
int sizeM = sizeof(M)/sizeof(M[0]) , sizeN = sizeof(N)/sizeof(N[0]);
int no_absent = transform(M,sizeM); //moves all the valid elements to the end and returns the number of elements absent
int m = no_absent , n = 0; // variables pointing at no_absent index and 0th index of M and N respectively
int l = 0; //to fill the M[]
while(n < sizeN and m < sizeM) //till any of the one array ends
{
if(M[m] <= N[n])
{
M[l++]=M[m++]; //assign the smaller and increase the index of that array
}
else
M[l++]=N[n++];
}
while(m < sizeM) //if some elements have remained in M then we can directly add them
M[l++] = M[m++];
while(n < sizeN) //if some elements have remained in N then we can directly add them
M[l++] = N[n++];
for(int i=0;i<sizeM;i++)
cout<<M[i]<<" ";
return 0;
}
```