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;
}
Try It

 


Next > < Prev
Scroll to Top