In merge two sorted arrays problem, we have 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 the second array.

## Example

**Input**

A[] = {1, 3, 5, 7, 9}

B[] = {2, 4, 6, 8, 10}

**Output**

A[] = {1, 2, 3, 4, 5}

B[] = {6, 7, 8, 9, 10}

**Explanation**

Merge array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Now we arrange them in the size of the given array. First n element in the first array and next m elements in the second array.

So, final arrays will be-

A[] = {1, 2, 3, 4, 5}

B[] = {6, 7, 8, 9, 10}

## Algorithm

If input arrays are A and B

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

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

- Move all elements one position ahead next to element found in array B.
- A[j+1] = A[j]
- Replace the next element of the element found with an element from array B.
- A[j+1] = B[i]
- Update element in B, B[i] = last.s

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

## C++ Program for Merge Two Sorted Arrays

#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; }

Input Arrays:- Array A: 1 3 5 7 9 Array B: 2 4 6 8 10 After Merge:- Array A: 1 2 3 4 5 Array B: 6 7 8 9 10

## Complexity Analysis for Merge Two Sorted Arrays

### Time Complexity

**O(n+m)** where n is the size of the first array and m is the size of the second array. Here we just traverse all the elements of both the array that’s why this logic leads us to O(n+m) time complexity.

### Space Complexity

**O(1)** because here we don’t use any auxiliary space here. Just replaces the values from one position to another.