Merge Two Sorted Arrays

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}

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.

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

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