Merging Two Sorted Arrays

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

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