# Merge two sorted arrays

## Merge two sorted arrays

Given two sorted arrays, the task is to merge them in a sorted manner.
Examples:

Input: arr1[] = { 1, 3, 4, 5}, arr2[] = {2, 4, 6, 8}
Output: arr3[] = {1, 2, 3, 4, 4, 5, 6, 8}
Input: arr1[] = { 5, 8, 9}, arr2[] = {4, 7, 8}
Output: arr3[] = {4, 5, 7, 8, 8, 9}

Method 1 (O(n1 * n2) Time and O(n1+n2) Extra Space)

1. Create an array arr3[] of size n1 + n2.
2. Copy all n1 elements of arr1[] to arr3[]
3. Traverse arr2[] and one by one insert elements (like insertion sort) of arr3[] to arr1[]. This step take O(n1 * n2) time.

We have discussed implementation of above method in Merge two sorted arrays with O(1) extra space
Method 2 (O(n1 + n2) Time and O(n1 + n2) Extra Space)
The idea is to use Merge function of Merge sort.

1. Create an array arr3[] of size n1 + n2.
2. Simultaneously traverse arr1[] and arr2[].
• Pick smaller of current elements in arr1[] and arr2[], copy this smaller element to next position in arr3[] and move ahead in arr3[] and the array whose element is picked.
3. If there are remaining elements in arr1[] or arr2[], copy them also in arr3[].

Below image is a dry run of the above approach:

Below is the implementation of the above approach:

 `// C++ program to merge two sorted arrays/` `#include` `using` `namespace` `std;` `// Merge arr1[0..n1-1] and arr2[0..n2-1] into` `// arr3[0..n1+n2-1]` `void` `mergeArrays(``int` `arr1[], ``int` `arr2[], ``int` `n1,` `                             ``int` `n2, ``int` `arr3[])` `{` `    ``int` `i = 0, j = 0, k = 0;` `    ``// Traverse both array` `    ``while` `(i

Output:

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

Time Complexity : O(n1 + n2)
Auxiliary Space : O(n1 + n2)

Method 3: Using Maps (O(nlog(n) + mlog(m)) Time and O(N) Extra Space)

1. Insert elements of both arrays in a map as keys.
2. Print the keys of the map.

Below is the implementation of above approach.

 `// C++ program to merge two sorted arrays` `//using maps` `#include` `using` `namespace` `std;` `// Function to merge arrays` `void` `mergeArrays(``int` `a[], ``int` `b[], ``int` `n, ``int` `m)` `{` `    ``// Declaring a map.` `    ``// using map as a inbuilt tool` `    ``// to store elements in sorted order.` `    ``map<``int``, ``bool``> mp;` `    ` `    ``// Inserting values to a map.` `    ``for``(``int` `i = 0; i < n; i++)` `    ``mp[a[i]] = ``true``;` `    ` `    ``for``(``int` `i = 0;i < m;i++)` `    ``mp[b[i]] = ``true``;` `    ` `    ``// Printing keys of the map.` `    ``for``(``auto` `i: mp)` `    ``cout<< i.first <<``" "``;` `}` `// Driver Code` `int` `main()` `{` `    ``int` `a[] = {1, 3, 5, 7}, b[] = {2, 4, 6, 8};` `    ` `    ``int` `size = ``sizeof``(a)/``sizeof``(``int``);` `    ``int` `size1 = ``sizeof``(b)/``sizeof``(``int``);` `    ` `    ``// Function call` `    ``mergeArrays(a, b, size, size1);` `    ` `    ``return` `0;` `}` `//This code is contributed by yashbeersingh42`

Output:

`1 2 3 4 5 6 7 8`

Time Complexity: O( nlog(n) + mlog(m) )
Auxiliary Space: O(N)

Last Updated on October 16, 2021 by admin

## Stock Buy Sell to Maximize ProfitStock Buy Sell to Maximize Profit

Stock Buy Sell to Maximize Profit The cost of a stock on each day is

## Sort an array of 0s, 1s and 2sSort an array of 0s, 1s and 2s

Sort an array of 0s, 1s and 2s Given an array A[] consisting 0s, 1s

## Maximum and minimum of an array using minimum number of comparisonsMaximum and minimum of an array using minimum number of comparisons

Maximum and minimum of an array using minimum number of comparisons   Write a C

## Print a given matrix in spiral formPrint a given matrix in spiral form

Print a given matrix in spiral form Given a 2D array, print it in spiral

## Multidimensional Arrays in JavaMultidimensional Arrays in Java

Multidimensional Arrays in Java Multidimensional Arrays can be defined in simple words as array of

## Find the Missing NumberFind the Missing Number

Find the Missing Number You are given a list of n-1 integers and these integers