## Problem

You are given two sorted arrays A and B of lengths m and n, the task is to merge the two sorted arrays in such a way that the merged array is also sorted.

## Example

**Input**

A[] = {3, 9, 10, 18, 23}

B[] = {5, 12, 15, 20, 21, 25}

**Output**

Merged[] = {3, 5, 9, 10, 12, 15, 18, 20, 21, 23, 25}

**Explanation**

The merged array is of the size of n + m and contains both the elements of array A and array B in sorted order

**Input:**

A[] = { 5, 8, 9}

B[] = {4, 7, 8}

**Output:**

Merged[] = {4, 5, 7, 8, 8, 9}

**Explanation**

The merged array is of the size of n + m and contains both the elements of array A and array B in sorted order

## Index

- Brute Force Approach
- Insertion Sort Approach
- Efficient Approach — Using Merge Sort

## Brute Force Approach

The idea is to create a new array C[] of length m+n and put all the elements from A[] and B[] in it and then sort them using Arrays.sort().

## Algorithm

- Create an array C of n+m size to store the merged array
- Put the values of both A and B arrays using a for loop
- Sort the C array using Array..sort().

## Pseudo Code

```
Int[] solve(int[] A, int[] B, int n, int m) {
Create a new array C of n+m size
while(i<n) {
C[k++] = A[i++];
}
while(j<m) {
C[k++] = B[j++];
}
Sort C;
return C
}
```

## Output

Array after merging - 1 2 3 4 5 6 7 8

**Time Complexity** — O((m+n) log(m+n))

We have sorted an array of size m+n using Arrays.sort(), and the time complexity of this operation is O(n log n) which in this case becomes O((m+n )log(m+n))

**Space Complexity** — O(m+n)

We have created a new array C of size n+m which will store the merged sorted array.

## Top comments (1)

Merge sort is one of the most efficient sorting algorithms. get out of jail spell