Merge Sorted Array

In merge sorted array problem we have given two sorted arrays in increasing order. In input first, we have given the number initialized to array1 and array2. These two-number are N and M. The size of array1 is equal to the sum of N and M. In array 1 first n number is initialized and next m are contained 0. We need to add the array2 in array1 such that the final array1 in remains increasing order. Let’s see the below format for better understanding.

Input Format

First-line containing two integer values N and M.

Second-line containing array1 in which first N numbers are initialized and next M numbers are 0.

The third line containing array2 which contains M numbers.

Output Format

Print the first array in a single line where values are separated by a gap.

Constraints

• 0<=N,M<=100000
• array1[i]<=|1000000000| where 0<=i<N and array1[i]=0 where N<=i<N+M.
• array2[i]<=|1000000000|

Sample Input:
5 3
2 3 4 4 8 0 0 0
3 5 7

Sample Output:
2 3 3 4 4 5 7 8

Explanation For Merge two sorted arrays

Here we are bound to can’t create any extra space if we create one more array to store the value in sorted order then we need to use linear space complexity. So, one simple approach to just add the second at the end of array1 and then sort the array1. In this, we cant create any extra space and find the solution in only O(N*logN) time.

Algorithm For Merge Sorted Array

Step:1 Set j=0
Step:2 For i in range N to N+M-1:
           a) array1[i]=array2[j]
           b) j=j+1
Step:3 Sort the array1
Step:4 Print the array1

Implementation For Merge Sorted Array

/*C++ Implementation of "Merge Sorted Array".*/ 
#include<bits/stdc++.h> 
using namespace std; 
int main() 
{
    /*input values.*/
    int n,m;
    cin>>n>>m;
    int array1[n+m];
    for(int i=0;i<n+m;i++)
    {
        cin>>array1[i];
    }
    int array2[m];
    for(int i=0;i<m;i++)
    {
        cin>>array2[i];
    }
    /*add array2 at the end of array1.*/
    int j=0;
    for(int i=n;i<n+m;i++)
    {
        array1[i]=array2[j];
        j++;
    }
    sort(array1,array1+n+m);
    /*print array1*/
    for(int i=0;i<n+m;i++)
    {
        cout<<array1[i]<<" ";
    }
    return 0;
}

7 5
1 2 2 5 8 9 17 0 0 0 0 0
2 5 13 19 21

1 2 2 2 5 5 8 9 13 17 19 21

Time Complexity

O(N*log N) because here we perform sorting which takes N*log N time for sort the N numbers. Here N is the size of array1. It depends only on the first array because we add the second array to the first array. The size of the 1st array is always greater than the 2nd array.

Space Complexity

O(1) because we don’t use any extra space rather than our input array. We just put all values in array1 whose size already given to us. So we just perform sorting and get our result without creating any extra space to merge two arrays.

References