# Merge an array of size n into another array of size m+n

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)