# Merge two arrays by satisfying given constraints

Given two sorted arrays X[] and Y[] of size m and n each where m >= n and X[] has exactly n vacant cells, merge elements of Y[] in their correct position in array X[] i.e. merge (X, Y) by keeping the sorted order.

For example,

Input:
X[] = { 0, 2, 0, 3, 0, 5, 6, 0, 0}
Y[] = { 1, 8, 9, 10, 15 }

The vacant cells in X[] is represented by 0

Output:
X[] = { 1, 2, 3, 5, 6, 8, 9, 10, 15 }

The idea is very simple. We initially move non-empty elements of `X[]` in the beginning of `X[]` and then merge `X[]` with `Y[]` starting from end. The merge process is similar to merge routine of the mergesort algorithm.

## Java

Output:

1 2 3 5 6 8 9 10 15

The time complexity of above solution is O(m + n) and auxiliary space used by the program is O(1).

Exercise: Merge arrays in descending order

(1 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Subscribe
Notify of
Guest

In the merge part you first merge from both arrays and then fill up from the second.
This can also done with the following code, which takes elements from both arrays until k = 0:

Guest
Tanmay Jha

I have solved by modifying the last question. Have a look if anybody wants to follow up last questions method.

#include

using namespace std;

void mergeSort(vector &x,vector &y,int m,int n){
int first,k,j;
for(int i=0;iy[0])
{
swap(x[i],y[0]);
first=y[0];
for(k=1;ky[k];k++)
y[k-1]=y[k];
y[k-1]=first;
}
}
else{
j=i;
while(x[j]==0)
j++;
if(j==m)
{
for(int w=0;wy[0]){
x[i]=y[0];
y.erase(y.begin());
}
else
swap(x[j],x[i]);
}
cout<<"\nX status is: ";
for(int i=0;i<x.size();i++)
cout<<x[i]<<" ";
cout<<endl;

cout<<"Y status is: ";
for(int i=0;i<y.size();i++)
cout<<y[i]<<" ";

}

}

int main(){

int X[]={0,2,0,3,0,5,6,0,0};
int Y[]={1,8,9,10,15};

vector x(X,X+sizeof(X)/sizeof(X[0]));
vector y(Y,Y+sizeof(Y)/sizeof(Y[0]));

cout<<"X status is: ";
for(int i=0;i<x.size();i++)
cout<<x[i]<<" ";
cout<<endl;

cout<<"Y status is: ";
for(int i=0;i<y.size();i++)
cout<<y[i]<<" ";

cout<<"\nAfter merge sort \n";
mergeSort(x,y,sizeof(X)/sizeof(X[0]),sizeof(Y)/sizeof(Y[0]));

cout<<"X status is: ";
for(int i=0;i<x.size();i++)
cout<<x[i]<<" ";
cout<<endl;

cout<<"Y status is: ";
for(int i=0;i<y.size();i++)
cout<<y[i]<<" ";

return 0;
}