Home » Technical Interview Questions » Array Interview Questions » Merging Two Sorted Arrays

Merging Two Sorted Arrays


Reading Time - 4 mins

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

READ  Sliding Window Maximum

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

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions