# Merge Sorted Array

You are given two integer arrays `nums1` and `nums2`, sorted in non-decreasing order, and two integers `m` and `n`, representing the number of elements in `nums1` and `nums2` respectively.

Merge `nums1` and `nums2` into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array `nums1`. To accommodate this, `nums1` has a length of `m + n`, where the first `m` elements denote the elements that should be merged, and the last `n` elements are set to `0` and should be ignored. `nums2` has a length of `n`.

## Problem Statement

The problem is to merge two given integer arrays `nums1` and `nums2`, which are sorted in non-decreasing order, into a single array. The merged array should also be sorted in non-decreasing order and should be stored in `nums1` array.

The length of `nums1` array is `m+n`, where `m` denotes the number of elements in `nums1`, and `n` denotes the number of elements in `nums2`. The first `m` elements of `nums1` should contain the merged sorted array, and the remaining `n` elements of `nums1` should be set to 0 and ignored.

The solution should not return the final sorted array, but instead, modify the `nums1` array in-place.

## Examples

Example 1:

```Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.
```

Example 2:

```Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].
```

Example 3:

```Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.```

## Clarifying Questions

1. Are the arrays nums1 and nums2 guaranteed to be of equal length?
2. Can we assume that the non-zero elements in nums1 are already sorted in non-decreasing order?
3. Can we assume that the non-zero elements in nums2 are already sorted in non-decreasing order?
4. Is it allowed to use additional data structures or do we need to perform the merge in-place?
5. Do we need to consider edge cases such as empty arrays or arrays with only zero elements?

## Solutions

There are several approaches that can be used to solve this problem:

1. Brute Force

2. Two-pointers

3. Merge and Sort

4. Merge and Insert

5. In-Place Merging

All of the above approaches can be used to solve this problem, but the best approach would depend on various factors like input size, time complexity, and space complexity requirements.

### Brute Force:

Iterate over both arrays, compare the elements at each index, and insert the smaller element into a new array until both arrays are exhausted. Then, copy the new array back into nums1.

#### Algorithm:

1. Initialize an empty array `merged`.
2. Initialize two pointers, `i` and `j`, to point to the first element of nums1 and nums2, respectively.
3. While both arrays have elements:
• If `nums1[i]` is smaller than or equal to `nums2[j]`, append `nums1[i]` to `merged` and increment `i`.
• Otherwise, append `nums2[j]` to `merged` and increment `j`.
4. If `nums1` still has elements, append the remaining elements to `merged`.
5. If `nums2` still has elements, append the remaining elements to `merged`.
6. Copy the elements from `merged` back into `nums1`.

Time complexity: O((m+n)^2)

Space complexity: O(m+n)

This approach involves creating a new array and iterating over both input arrays to add elements to the new array, while keeping it sorted. For each element in the second array, we compare it with each element in the first array and insert it in the correct position. The time complexity of this approach is O((m+n)^2), because for each element in the second array we have to compare it to all the elements in the first array. The space complexity is O(m+n), because we create a new array to store the merged elements. This approach is not efficient and is not practical for large inputs, but it is simple to implement.

### Two-pointers:

Initialize two pointers, one for each array, and iterate over both arrays, comparing the elements at each pointer's current position. The smaller element is inserted into nums1, and the corresponding pointer is moved one position to the right. This process continues until one of the arrays is exhausted. Then, copy the remaining elements from the non-exhausted array into nums1.

#### Algorithm:

1. Initialize two pointers, `i` and `j`, to point to the first element of nums1 and nums2, respectively.
2. While both arrays have elements:
• If `nums1[i]` is smaller than or equal to `nums2[j]`, increment `i`.
• Otherwise, shift the elements in `nums1` from index `i` to `m+j` one position to the right and insert `nums2[j]` at index `i`. Increment `i` and `j`.
3. If `nums2` still has elements, copy the remaining elements to `nums1`.

Time complexity: O(m+n)

Space complexity: O(1)

This approach involves traversing the two arrays using two pointers until all the elements have been merged. It is a linear-time algorithm and has a space complexity of O(1) because it does not use any additional data structures.

### Merge and Sort:

Merge the two arrays into a new array, then sort the new array, and copy the sorted elements back into nums1.

#### Algorithm:

1. Merge the two arrays into a new array, `merged`.
2. Sort the `merged` array.
3. Copy the elements from `merged` back into `nums1`.

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

Space complexity: O(m+n)

This approach involves merging the two arrays and then sorting the resulting array. The time complexity is dominated by the sorting algorithm used, which is usually O((m+n)log(m+n)). The space complexity is O(m+n) because a new array is created to store the merged and sorted elements.

### In-Place Merging:

Starting from the end of nums1, compare the last elements of both arrays and insert the larger element at the end of nums1. Move the pointer of the array that contains the larger element to the left and repeat until one of the arrays is exhausted. Then, copy the remaining elements from the non-exhausted array into nums1.

#### Algorithm:

1. Initialize two pointers, `i` and `j`, to point to the last non-zero element of nums1 and nums2, respectively.
2. Initialize a pointer, `k`, to point to the last element of nums1.
3. While both `i` and `j` are non-negative:
• If `nums1[i]` is greater than `nums2[j]`, copy `nums1[i]` to `nums1[k]` and decrement `i`. Otherwise, copy `nums2[j]` to `nums1[k]` and decrement `j`.
• Decrement `k`.
4. If `j` is still non-negative, copy the remaining elements from `nums2` to `nums1`.
This approach involves starting from the end of both arrays and inserting the largest element from either `nums1` or `nums2` into the end of the merged array, until all elements have been inserted. This approach has a time complexity of O(m+n), which is more efficient than the Merge and Sort approach.

Time complexity: O(m+n)

Space complexity: O(1)

This approach involves merging the two arrays in-place, by starting from the end of both arrays and inserting the largest element into the end of the first array. The time complexity is O(m+n) because each element is compared and inserted once. The space complexity is O(1) because no additional data structures are used.

The most optimal approach is the Two Pointers Approach, also known as the In-Place Merging Approach, with a time complexity of O(m + n) and a space complexity of O(1). This approach merges the two sorted arrays in place without the need for extra space, and it runs in linear time, making it the most efficient approach for this problem. The other approaches require additional space or sorting, resulting in higher time and space complexity.
Share: