Merging two sorted arrays

Given two sorted arrays, one array with size m+n and the other array with size n. We will merge the n sized array into m+n sized array and print the m+n sized merged array.

Example :

Input : M[] = {1, 7, absent, absent, 124, 132, absent, 155, 200};

N[] = {2,4,152};

Output : {1, 2, 4, 7, 124, 132, 152, 155, 200}

Algorithm

Let the arrays be M[] and N[]. Size of M[] be m+n and Size of N[] be n
1. First, move the non absent elements in M[] to the end and return the number of elements that are absent ie, store it in j
2. Start from the jth element of the array M[] and 0th element of the array N[] and compare each value of the two arrays, and store the elements in M[] in ascending order

Time Complexity 

O(m+n), where m and n are sizes of the arrays . 

C++ Program

#include <bits/stdc++.h>
#define absent INT_MAX
using namespace std;

int transform(int M[],int n)
{
	int j = n-1;
	for(int i=n-1;i>=0;i--)
	{
		if(M[i] != absent)
		{
			M[j]=M[i];
			j--;
		}
	}
	return (j+1); //jth index implies (j+1) elements absent
}
int main()
{
	int M[] = {1, 7, absent, absent, 124, 132, absent, 155, 200};
	int N[] = {2,4,152,360};
	int sizeM = sizeof(M)/sizeof(M[0]) , sizeN = sizeof(N)/sizeof(N[0]);
	
	int no_absent = transform(M,sizeM); //moves all the valid elements to the end and returns the number of elements absent	
	
	int m = no_absent , n = 0; // variables pointing at no_absent index and 0th index of M and N respectively
	int l = 0; //to fill the M[]
	
	while(n < sizeN and m < sizeM) //till any of the one array ends
	{
	
		if(M[m] <= N[n]) 
			{
				M[l++]=M[m++];  //assign the smaller and increase the index of that array
			}
		else
			M[l++]=N[n++];
	}
	
	while(m < sizeM) //if some elements have remained in M then we can directly add them
		M[l++] = M[m++];
	while(n < sizeN) //if some elements have remained in N then we can directly add them
		M[l++] = N[n++];
		
	for(int i=0;i<sizeM;i++)
		cout<<M[i]<<" ";
		
	return 0;
}
Try It


Next > < Prev
Scroll to Top