# Merging Two Sorted Arrays

Difficulty Level Easy
ArrayViews 983

## Problem Statement

In merging two sorted arrays problem we have 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

6 3

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

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

Output

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

## Approach

Here we first set all the absent elements at the end of the big size array. After fixing elements then we select one element from M array and one element from N array and pick the smallest element and put it in the exact position in the M array. Pick all the elements and put them in the correct position. Here some cases arise one array visited and some elements remaining unvisited in another array. Then we like Once we set all the elements then we need to print the M array (big size array) whose size n+m.

## Algorithm for Merging Two Sorted Arrays

Let the arrays be M[] and N[]. Size of M[] be m+n and Size of N[] be n
1. First, set pointer to s
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

## Implementation

### C++ Program for Merging Two Sorted Arrays

```#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};
int sizeM = sizeof(M)/sizeof(M) , sizeN = sizeof(N)/sizeof(N);

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

### Java Program for Merging Two Sorted Arrays

```import java.util.Scanner;
import java.util.Stack;
class sum
{
public static int transform(int M[],int n)
{
int j = n-1;
for(int i=n-1;i>=0;i--)
{
if(M[i] != -1)
{
M[j]=M[i];
j--;
}
}
return (j+1); //jth index implies (j+1) elements absent
}
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int m = sr.nextInt();
int a[] = new int[n+m+1];
int b[] = new int[m];
for(int i=0;i<(n+m);i++)
{
a[i] = sr.nextInt();
}
for(int i=0;i<m;i++)
{
b[i] = sr.nextInt();
}
int no_absent = transform(a,n+m); //moves all the valid elements to the end and returns the number of elements absent

int m1 = no_absent , n1 = 0; // variables pointing at no_absent index and 0th index of M and N respectively
int l = 0; //to fill the M[]
while((n1 < m) && (m1 < (m+n))) //till any of the one array ends
{
if(a[m1] <= b[n1])
{
a[l++]=a[m1++];  //assign the smaller and increase the index of that array
}
else
a[l++]=b[n1++];
}
while(m1 < (m+n)) //if some elements have remained in M then we can directly add them
a[l++] = a[m1++];
while(n1 < m) //if some elements have remained in N then we can directly add them
a[l++] = b[n1++];
for(int i=0;i<(m+n);i++)
System.out.print(a[i]+" ");
System.out.println();
}
}```
```6 3
1 7 -1 -1 124 132 -1 155 200
2 4 152```
`1 2 4 7 124 132 152 155 200`

## Complexity Analysis for Merging Two Sorted Arrays

### Time Complexity

O(m+n), where m and n are sizes of the arrays. Here we traverse both the arrays exactly one time which leads us to linear time complexity.

### Space Complexity

O(1) because we don’t use any auxiliary space here. That’s why the above logic leads us to constant time complexity.

References

Translate »