# Merge Two Sorted Arrays

## Problem Statement

Given two sorted arrays A[] and B[] of size N and M. The task is to merge both the arrays into a single array in non-decreasing order.

Examples:

Input: A[] =[3, 9, 10, 18, 23], B[] = [5, 12, 15, 20, 21, 25]
Output: [3, 5, 9, 10, 12, 15, 18, 20, 21, 23, 25]
Explanation: The merged array contains all the elements from both arrays in sorted order.

Input:  A[] = [1, 5], B[] = [4, 6, 7]
Output: [1, 4, 5, 6, 7]

## Insert and Sort Approach

The most naive approach is to simply merge elements of one array into another and sort the resultant array.

### C++ Code

```  void merge(int nums1[], int m, int nums2[], int n) {
for (int i = 0; i < n; i++) {
nums1[i + m] = nums2[i];
}
sort(nums1, nums1 + n + m);
}```

### Java Code

```public void merge(int[] nums1, int m, int[] nums2, int n) {
for (int i = 0; i < n; i++) {
nums1[i + m] = nums2[i];
}
Arrays.sort(nums1);
}```

### Python Code

```def merge(nums1, m, nums2, n)
for i in range(n):
nums1[i + m] = nums2[i]

nums1.sort()```

Time Complexity:O((N + M)log(N+M)), where N and M are the size of array A[] and B[]
Space Complexity:O(N), built-in sort takes space

## Merge Sort Method

The key idea to note here is that both the arrays are sorted. Therefore, taking advantage of this fact, we can apply a method similar to the merge sort technique.
Create an auxiliary array of size N + M and insert the merge element in this array.

Let us understand this approach with an example:

Algorithm

• Create an auxiliary array of size N + M.
• Put two pointers i and j and initialise them to 0.
• Pointer i points to the first array, whereas pointer j points to the second array.
• Traverse both the array simultaneously using the pointers, and pick the smallest elements among both the array and insert in into the auxiliary array.
• Increment the pointers.
• After traversal, return the merged array.

### C++ Implementation

```void mergeArrays(int arr1[], int arr2[], int n1,
int n2, int arr3[]) {
int i = 0, j = 0, k = 0;
while (i < n1 && j < n2) {
if (arr1[i] < arr2[j])
arr3[k++] = arr1[i++];
else
arr3[k++] = arr2[j++];
}
while (i < n1)
arr3[k++] = arr1[i++];

while (j < n2)
arr3[k++] = arr2[j++];
}```

### Java Implementation

```public static void mergeArrays(int[] arr1, int[] arr2, int n1,
int n2, int[] arr3) {
int i = 0, j = 0, k = 0;
while (i < n1 && j < n2) {
if (arr1[i] < arr2[j])
arr3[k++] = arr1[i++];
else
arr3[k++] = arr2[j++];
}
while (i < n1)
arr3[k++] = arr1[i++];

while (j < n2)
arr3[k++] = arr2[j++];
}```

### Python Implementation

```def mergeArrays(arr1, arr2, n1, n2):
arr3 = [None] * (n1 + n2)
i = 0
j = 0
k = 0

while i < n1 and j < n2:
if arr1[i] < arr2[j]:
arr3[k] = arr1[i]
k = k + 1
i = i + 1
else:
arr3[k] = arr2[j]
k = k + 1
j = j + 1

while i < n1:
arr3[k] = arr1[i]
k = k + 1
i = i + 1

while j < n2:
arr3[k] = arr2[j]
k = k + 1
j = j + 1```

Time Complexity:O(N + M), where N and M is the size of array A[] and B[]
Space Complexity:O(N + M), as the auxiliary array is used

## FAQs

How is the space complexity O(1) for the two-pointers approach?
Since, we are in placing merging all the elements into the first array, without creating any other auxiliary space, the space complexity is O(1)

How is the two pointer approach different from the merge sort approach?
The merge sort approach considers an auxiliary array to sort and keeps two-pointer and the beginning of the array and merges accordingly.

Whereas, the two-pointer approach, starts iterating from backward and keeps merging the elements in place.

##### Previous Post ## Top 10 ​​​​Data Mining Tools

##### Next Post 