Home » Interview Questions » Array Interview Questions » Merge two sorted arrays

Merge two sorted arrays


()

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 second array.

Example

Input arrays are

All the elements in sorted order: [1, 2, 3, 4, 5, 6, 7, 8, 9 ,10]

Arrange them in A and B,

Output

 

Time Complexity : O(m+n), m and n are sizes of the arrays.

Algorithm

If input arrays are A and B

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

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

a)    Move all elements one position ahead next to element found in array B.

A[j+1] = A[j]

b)    Replace next element of element found with element from array B.

A[j+1] = B[i]

c)    Update element in B, B[i] = last.s

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

Algorithm working

C++ Program

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

READ  Power of Two

 

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

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