# Merge Two Sorted Arrays

Difficulty Level Medium
Array Two PointerViews 1915

## 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```

### 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.

### Space Complexity

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

References

Translate »