Hello Everyone,

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.

Input: array with m+n elements (mPlusN[]).

NA => Value is not filled/available in array mPlusN[]. There should be n such array blocks.

Input: array with n elements (N[]).

Output: N[] merged into mPlusN[] (Modified mPlusN[])

**Algorithm:**

Let first array be mPlusN[] and other array be N[] 1) Move m elements of mPlusN[] to end. 2) Start from nth element of mPlusN[] and 0th element of N[] and merge them into mPlusN[].

Below is the implementation of the above algorithm :

`// C++ program to Merge an array of`

`// size n into another array of size m + n`

`#include <bits/stdc++.h>`

`using`

`namespace`

`std;`

`/* Assuming -1 is filled for the places`

` `

`where element is not available */`

`#define NA -1`

`/* Function to move m elements at`

` `

`the end of array mPlusN[] */`

`void`

`moveToEnd(`

`int`

`mPlusN[], `

`int`

`size)`

`{`

` `

`int`

`j = size - 1;`

` `

`for`

`(`

`int`

`i = size - 1; i >= 0; i--)`

` `

`if`

`(mPlusN[i] != NA)`

` `

`{`

` `

`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 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`

`((j == n)||(i < (m + n) && mPlusN[i] <= N[j]))`

` `

`{`

` `

`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)`

`{`

` `

`for`

`(`

`int`

`i = 0; i < size; i++)`

` `

`cout << arr[i] << `

`" "`

`;`

` `

`cout << endl;`

`}`

`/* Driver code */`

`int`

`main()`

`{`

` `

`/* Initialize arrays */`

` `

`int`

`mPlusN[] = {2, 8, NA, NA, NA, 13, NA, 15, 20};`

` `

`int`

`N[] = {5, 7, 9, 25};`

` `

` `

`int`

`n = `

`sizeof`

`(N) / `

`sizeof`

`(N[0]);`

` `

`int`

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

`}`

**Output**

2 5 7 8 9 13 15 20 25

**Time Complexity:** O(m+n)