Merge Two Sorted Arrays  

Difficulty Level Medium
Frequently asked in Adobe Amazon Apple Bloomberg ByteDance Cisco eBay Facebook Goldman Sachs Google IBM LinkedIn lyft Microsoft Oracle Uber VMware Walmart Labs Wish Yahoo Yandex
Array Two Pointer

Problem Statement  

In merge two sorted arrays problem, we have given two input sorted arrays, we need to merge these two arrays such that the initial numbers after complete sorting should be in the first array and remaining in the second array.

Example  

Input

A[] = {1, 3, 5, 7, 9}

B[] = {2, 4, 6, 8, 10}

Please click Like if you loved this article?

Output

A[] = {1, 2, 3, 4, 5}

B[] = {6, 7, 8, 9, 10}

Explanation

Merge array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Now we arrange them in the size of the given array. First n element in the first array and next m elements in the second array.

So, final arrays will be-

A[] = {1, 2, 3, 4, 5}

B[] = {6, 7, 8, 9, 10}

Algorithm  

If input arrays are A and B

1. Run the loop through the B array from the last element. In (B[]) for all B[i]

2. Compare the elements starting from last of array A with the last element of B and if any element found less than the last element of B. last = A[i], find A[j] < B[i].

  • Move all elements one position ahead next to element found in array B.
  • A[j+1] = A[j]
  • Replace the next element of the element found with an element from array B.
  • A[j+1] = B[i]
  • Update element in B, B[i] = last.s
See also
Find Three Element From Different Three Arrays Such That a + b + c = sum

3. Apply function on given input arrays, and Print the arrays.

Implementation  

C++ Program for Merge Two Sorted Arrays

#include <bits/stdc++.h>
using namespace std;
//Merge function, arrays are A[],B[] and sizes M and N respectively
void Merge(int A[], int B[], int M, int N)
{
    //for all elements in B from last
    for(int i=N-1; i>=0; i--)
        {
            int j, last = A[M-1];
            // Moving elements one position ahead.
            for(j=M-2;j >= 0 && A[j]>B[i];j--)
                {
                    A[j+1] = A[j];
                }
            //Move next element and update element in B
            if(j!=M-2 || last > B[i])
                {
                    A[j+1] = B[i];
                    B[i] = last;
                }
        }
}
//function to print the given array
int PrintArray(int array[],int N)
{
    for (int i=0; i<N; i++)
       {
           cout <<array[i]<<" ";
       }
}
//Main function: To call functions on input array
int main(void)
{
    int A[] = {1, 3, 5, 7, 9};
    int B[] = {2, 4, 6, 8, 10};
    int M = sizeof(A)/sizeof(A[0]);
    int N = sizeof(B)/sizeof(B[0]);
    cout << "Input Arrays:-";
    cout << "\nArray A: ";
    PrintArray(A,M);
    cout << "\nArray B: ";
    PrintArray(B,N);
   
   //Mergeing A, B according to the condition
    Merge(A, B, M, N);
    
    cout << "\nAfter Merge:-";
    cout << "\nArray A: ";
    PrintArray(A,M);
    cout << "\nArray B: ";
    PrintArray(B,N);
    return 0;
}
Input Arrays:-
Array A: 1 3 5 7 9 
Array B: 2 4 6 8 10 
After Merge:-
Array A: 1 2 3 4 5 
Array B: 6 7 8 9 10

Java Program for Merge Two Sorted Arrays

import static java.lang.Math.pow;
import java.util.Scanner;
class sum
{
    //Merge function, arrays are A[],B[] and sizes M and N respectively
    public static void Merge(int A[], int B[], int M, int N)
    {
        //for all elements in B from last
        for(int i=N-1; i>=0; i--)
            {
                int j, last = A[M-1];
                // Moving elements one position ahead.
                for(j=M-2;j >= 0 && A[j]>B[i];j--)
                    {
                        A[j+1] = A[j];
                    }
                //Move next element and update element in B
                if(j!=M-2 || last > B[i])
                    {
                        A[j+1] = B[i];
                        B[i] = last;
                    }
            }
    }
    //function to print the given array
    public static void PrintArray(int array[],int N)
    {
        for (int i=0; i<N; i++)
           {
               System.out.print(array[i]+" ");
           }
    }
    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];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int b[] = new int[n];
        for(int i=0;i<n;i++)
        {
            b[i] = sr.nextInt();
        }
        //Mergeing A, B according to the condition
        Merge(a, b, n, m);
        System.out.println("\nAfter Merge:-");
        System.out.print("\nArray A: ");
        PrintArray(a,n);
        System.out.print("\nArray B: ");
        PrintArray(b,m);
        System.out.println();
    }
}
5 5
1 3 5 7 9
2 4 6 8 10
After Merge:-

Array A: 1 2 3 4 5 
Array B: 6 7 8 9 10

Complexity Analysis for Merge Two Sorted Arrays  

Time Complexity

O(n+m) where n is the size of the first array and m is the size of the second array. Here we just traverse all the elements of both the array that’s why this logic leads us to O(n+m) time complexity.

See also
Rearrange array such that even index elements are smaller and odd index elements are greater

Space Complexity

O(1) because here we don’t use any auxiliary space here. Just replaces the values from one position to another.

Please click Like if you loved this article?

References

Please click Like if you loved this article?