## Introduction

In this blog, we will discuss the problem of merging two unsorted arrays into a single sorted array. For this, we will have a look and understand the following two approaches:

**Brute force:**We first store all the elements into the final array and then sort the array.**Two pointers:**Here, we first individually sort the two arrays and then, using two pointers, store them in the final array.

**Two pointers:** The two-pointer technique uses two variables for iterating over array/arrays. Here, it assumes that the array we are traversing over is sorted. This technique is widely used for finding pairs of elements with a given sum. In this problem, we have used this technique over two different arrays to store the elements of these arrays in a sorted manner.

### Problem Statement

The problem above states that given two unsorted arrays, we have to merge them into a single sorted array.

### Sample Example

**Input 1: **

```
a[] = {2,5,4,7}
b[] = {1,6,3}
```

**Output 1:**

`Merged list: {1,2,3,4,5,6,7}`

**Explanation:**

`In the above example, we see that the final array is sorted.`

**Input 2:**

```
a[] = {1,100,2}
b[] = {2,21,3}
```

**Output 2:**

`Merged List: {1,2,2,3,21,100}`

**Explanation:**

`In the above example, we see that the final array (Merged List) is sorted.`

## Brute Force Approach

In the brute force approach, we first store all the elements in a temp array, then sort them. Below is the solution:

- Create a temp array.
- Store all the elements in this array.
- Sort the array.

### Pseudocode

```
temp[n+m]
k = 0
for i = 1 to n:
temp[k] = a[i]
k+=1
for j = 1 to m:
temp[k] = b[j]
k+=1
sort(temp, temp + n + m)
```

### Implementation in C++

```
#include "bits/stdc++.h"
using namespace std;
void solve()
{
//Defining the 2 arrays
int a[] = {2,5,4,7};
int b[] = {1,6,3};
int n = sizeof(a)/sizeof(int);
int m = sizeof(b)/sizeof(int);
//Creating a temp array
int temp[n+m];
int k = 0;
//Storing elements from first array in temp
for(auto i: a){
temp[k]=i;k+=1;
}
//Storing elements from second array in temp
for(auto i: b){
temp[k]=i;k+=1;
}
//Sorting the temp array
sort(temp, temp+n+m);
cout<<"Merged List: ";
for(auto i: temp){
cout<<i<<" ";
}
}
int main()
{
solve();
return 0;
}
```

**Output:**

`Merged List: 1 2 3 4 5 6 7`

### Implementation in Python

```
def solve(a,b):
n = len(a)
m = len(b)
#First, we define our array.
temp = [0 for i in range(n+m)]
k = 0
#Storing the elements of both these array into the final array
for i in a:
temp[k] = i
k+=1
for j in b:
temp[k] = j
k+=1
#Sorting the final array.
temp.sort()
#Printing the final array.
print("Merged List: ")
for i in temp:
print(i, end = " ")
# Driver code
a = [ 2,5,4,7]
b = [1,6,3]
solve(a,b)
```

**Output**:

`Merged List: 1 2 3 4 5 6 7`

### Complexity Analysis

**Time complexity**: O((n+m) * log (n+m))

**Explanation: **From the above solution, we see that:

- First, we store all the elements from both arrays in the temp array. This takes O(n+m) time.
- Sort the final array, i.e., the temp array. This takes O((n+m)*log(n+m)).

Therefore, the total time complexity becomes O((n+m)*log(n+m)) + O(n+m), which equals to

O((n+m)*log(n+m)).

**Space complexity:** O(n+m)

**Explanation: **As in the above approach, we had created a temp array to store the final sorted sequence of elements. Therefore, the space complexity of the above array becomes O(n+m).

Also Read - __Selection Sort in C__