# Merge two sorted arrays

## 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.

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

Scroll to Top