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