## Given two input sorted arrays, we need to merge these two arrays such that the initial numbers after complete sorting should be in the first array and remaining in second array.

### Example

**Input arrays are**

All the elements in sorted order: [1, 2, 3, 4, 5, 6, 7, 8, 9 ,10]

Arrange them in A and B,

**Output**

**Time Complexity : O(m+n), m and n are sizes of the arrays.**

## Algorithm

If input arrays are A and B

**Step 1 :** Run loop through the B array from last element. In (B[]) for all B[i]

**Step 2 :** compare the elements starting from last of array A with last element of B and if any element found less than last element of B. last = A[i], find A[j] < B[i].

a)Â Â Â Move all elements one position ahead next to element found in array B.

A[j+1] = A[j]

b)Â Â Â Replace next element of element found with element from array B.

A[j+1] = B[i]

c)Â Â Â Update element in B, B[i] = last.s

**Step 3 :** Apply function on given input arrays, and Print the arrays.

### Algorithm working

## C++ Program

#include <bits/stdc++.h> using namespace std; //Merge function, arrays are A[],B[] and sizes M and N respectively void Merge(int A[], int B[], int M, int N) { //for all elements in B from last for(int i=N-1; i>=0; i--) { int j, last = A[M-1]; // Moving elements one position ahead. for(j=M-2;j >= 0 && A[j]>B[i];j--) { A[j+1] = A[j]; } //Move next element and update element in B if(j!=M-2 || last > B[i]) { A[j+1] = B[i]; B[i] = last; } } } //function to print the given array int PrintArray(int array[],int N) { for (int i=0; i<N; i++) { cout <<array[i]<<" "; } } //Main function: To call functions on input array int main(void) { int A[] = {1, 3, 5, 7, 9}; int B[] = {2, 4, 6, 8, 10}; int M = sizeof(A)/sizeof(A[0]); int N = sizeof(B)/sizeof(B[0]); cout << "Input Arrays:-"; cout << "\nArray A: "; PrintArray(A,M); cout << "\nArray B: "; PrintArray(B,N); //Mergeing A, B according to the condition Merge(A, B, M, N); cout << "\nAfter Merge:-"; cout << "\nArray A: "; PrintArray(A,M); cout << "\nArray B: "; PrintArray(B,N); return 0; }