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

Merge Two Sorted Arrays


Reading Time - 3 mins

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}

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

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

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

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.

READ  Median of Two Sorted Arrays

Space Complexity

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

References

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