Merging Two Sorted Arrays

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.



6 3

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

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


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


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

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)
  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
  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.


Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions