Merging two sorted arrays code in c++.

June 23, 2019

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}

Note:- Readers are requested to submit their codes in comment section below in different languages. Best codes will be selected and published on the website.

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 .

Code

[code language=”cpp”]

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

[/code]