# Merge Two Sorted Arrays using Recursion

In this article, we will discuss how we can merge two sorted arrays into one sorted array using recursion.

Example

```Input
Array 1: { 1 , 2 , 5 , 6 }
Array 2: { 2 , 3 , 4 , 7 }

Output
Array 3: { 1 , 2 , 2 , 3 , 4 , 5 , 6 , 7 }```

The logic to merge two sorted arrays using recursion is the same as merging two sorted arrays using a while loop.

Suppose Array 1 and Array 2 are the input array and Array 3 is the output array.

We compare the elements of Array 1 and Array 2 and push them in Array 3 accordingly.

Each recursive call performs 1 comparison. If a recursive call compares ith index of Array 1 and jth index of Array 2 then the next recursive call will compare
(i+1)th index of Array 1 and jth index of Array 2 OR
ith index of Array 1 and (j+1)th index of Array 2

If there’s no element left to compare in one of the Array, we push the remaining elements of other Array to Array 3 and stop the recursive calls.

## Program to Merge Two Sorted Arrays using Recursion

``````#include<iostream>
#include<vector>
using namespace std;

// n: length of array 1
// m: Length of array 2
// i: current index of array 1
// j: current index of array 2
// k: current index of array 3
// array1, array2: input array that are being merged
// array3: output array
void MergeArrayRecursively(int array1[], int n, int array2[], int m, int array3[], int i, int j,int k ){

// checking if there are elements to compare
if(i<n&&j<m){

// compares array1[i] and array2[j]
// push the smaller elements to array3 and move to next index
if(array1[i]<array2[j]){
array3[k] = array1[i];
++i;
}
else{
array3[k] = array2[j];
++j;
}

++k;
MergeArrayRecursively(array1,n,array2,m,array3,i,j,k);

}
else{

// this code segment will run if there's no element left to compare
// in array 1 or array 2
// we push the remaining elements of other array to array 3
while(i<n){
array3[k] = array1[i];
++i;
++k;
}

while(j<m){
array3[k] = array2[j];
++j;
++k;
}

}

}

void PrintArray(int array[], int n){
for(int i=0;i<n;++i)
cout<<array[i]<<" ";
cout<<"\n\n";
}

int main() {
int n,m;
int array3[100];
int array1[] = { 1 , 3 , 8 , 9 , 14};
int array2[] = { 2 , 6, 7 , 15 , 16 };
n = sizeof(array1)/sizeof(int);	// length of array 1
m = sizeof(array2)/sizeof(int); // Length of array 2

cout<<"Array 1: "<<endl;
PrintArray(array1, n);
cout<<"Array 2: "<<endl;
PrintArray(array2, m);

MergeArrayRecursively(array1,n,array2,m,array3,0,0,0);

cout<<"Array Obtained By Merging Array 1 and Array2: "<<endl;
PrintArray(array3,n+m);

}``````

Output

Reference

Merging Two Arrays