There are 2 sorted arrays of size m and m+n respectively. First array (of size m) has m elements and Second array (of size m+n) has only n elements (last m positions are blank). So, the total number of elements in both the arrays is m+n (m in first and n in second). Write code to merge the m+n elements in the 2^{nd} array such that the result is sorted.

If the two arrays are as below:

Then the output should be:

### Solution:

**Start the backward merge, of array arr1 and n elements on arr2 into arr2 (Complete array, till position m+n) **

**Algorithm:**

1. Let a, b & c be three pointers.

- a points to last (m
^{th}) element of arr1 - b points to n
^{th}(last valid) element of arr2 - c points to the last empty position of arr2 (m+n)
^{th}

2. While ( a>=0 && b>=0). i.e will we have elements in both the arrays

If (arr1[a] > arr2[b]) arr2[c] = arr1[a] a-- else arr2[c] = arr2[b] b-- c--

3. If a >=0

Move remaining elements from arr1 to arr2 starting from a in arr1 to position c in arr2 in backward fashion

**Code:**

/** size of array arr2 should be m+n (and not n) */ void mergeIntoSecond(int * arr1, int m, int*arr2, int n) { int a=m-1, b=n-1, c=m+n-1; while(a>=0 && b>=0) { if(arr1[a] > arr2[b]) { arr2[c] = arr1[a]; a--; } else { arr2[c] = arr2[b]; b--; } c--; } for(;a>=0;a--, c--) arr2[c] = arr1[a]; }