# Merge Sorted Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/merge-sorted-array)
Canonical: https://scaleengineer.com/dsa/problems/merge-sorted-array
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Adobe](https://scaleengineer.com/companies/adobe), [Agoda](https://scaleengineer.com/companies/agoda), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Atlassian](https://scaleengineer.com/companies/atlassian), [Avito](https://scaleengineer.com/companies/avito), [Barclays](https://scaleengineer.com/companies/barclays), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [ByteDance](https://scaleengineer.com/companies/bytedance), [Cisco](https://scaleengineer.com/companies/cisco), [Cognizant](https://scaleengineer.com/companies/cognizant), [Criteo](https://scaleengineer.com/companies/criteo), [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [Expedia](https://scaleengineer.com/companies/expedia), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [HCL](https://scaleengineer.com/companies/hcl), [Hubspot](https://scaleengineer.com/companies/hubspot), [IBM](https://scaleengineer.com/companies/ibm), [Infosys](https://scaleengineer.com/companies/infosys), [Intel](https://scaleengineer.com/companies/intel), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [Palo Alto Networks](https://scaleengineer.com/companies/palo-alto-networks), [PayPal](https://scaleengineer.com/companies/paypal), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [ServiceNow](https://scaleengineer.com/companies/servicenow), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Wipro](https://scaleengineer.com/companies/wipro), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex), [Zoho](https://scaleengineer.com/companies/zoho), [athenahealth](https://scaleengineer.com/companies/athenahealth), [persistent systems](https://scaleengineer.com/companies/persistent-systems), [tcs](https://scaleengineer.com/companies/tcs), [Netflix](https://scaleengineer.com/companies/netflix), [Virtusa](https://scaleengineer.com/companies/virtusa), [Swiggy](https://scaleengineer.com/companies/swiggy), [Squarespace](https://scaleengineer.com/companies/squarespace), [VK](https://scaleengineer.com/companies/vk), [Canonical](https://scaleengineer.com/companies/canonical)
---
## Problem
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`.

**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.

**Constraints:**

* `nums1.length == m + n`
* `nums2.length == n`
* `0 <= m, n <= 200`
* `1 <= m + n <= 200`
* `-109 <= nums1[i], nums2[j] <= 109`

**Follow up:** Can you come up with an algorithm that runs in `O(m + n)` time?

# Approaches
## Merge and Sort
The most straightforward approach is to first merge the two arrays and then sort the resulting array. We can copy the elements of `nums2` into the available space at the end of `nums1` and then use a standard library sorting function to sort the entire `nums1` array.
**Time:** O((m+n) log(m+n)) · **Space:** O(log(m+n)) to O(m+n)
**Pros:** Simple to understand and implement.; Leverages highly optimized built-in sorting functions.
**Cons:** Inefficient as it doesn't utilize the fact that the input arrays are already sorted.; Time complexity is higher than the optimal solution.
### Explanation
This method ignores the sorted nature of the input arrays. It first combines the two lists into one and then applies a general-purpose sorting algorithm.

1.  **Copy `nums2`**: The `n` elements of `nums2` are copied to the end of `nums1`, which has `n` zero-padded slots available from index `m` to `m + n - 1`.
2.  **Sort `nums1`**: After copying, `nums1` contains all the elements from both original arrays, but it is not sorted. A call to a standard sorting function, like `java.util.Arrays.sort()`, is made to sort the entire `nums1` array of length `m + n`.

```java
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // Copy elements of nums2 into the end of nums1
        for (int i = 0; i < n; i++) {
            nums1[m + i] = nums2[i];
        }
        // Sort the entire nums1 array
        java.util.Arrays.sort(nums1);
    }
}
```
### Algorithm
*   Copy the `n` elements from `nums2` into `nums1` starting from index `m`.
*   Use a standard sorting algorithm (like `Arrays.sort()` in Java) to sort the first `m + n` elements of `nums1`.

## Merge with Auxiliary Array
A better approach is to use the fact that the arrays are sorted. We can iterate through both arrays using pointers and place the elements into a temporary array in sorted order. To perform this 'in-place' on `nums1`, we first need to copy the original `m` elements of `nums1` to a separate array to avoid overwriting them during the merge process. Then, we merge the copied array and `nums2` back into `nums1`.
**Time:** O(m+n) · **Space:** O(m)
**Pros:** Achieves linear time complexity, O(m+n).; Conceptually straightforward, similar to the merge step of the standard merge sort algorithm.
**Cons:** Requires extra space proportional to the number of initial elements in `nums1`, which violates the O(1) space constraint for a truly in-place solution.
### Explanation
This approach respects the sorted property of the arrays to achieve a linear time merge. However, merging from the beginning into `nums1` would overwrite its elements before they are used for comparison. To solve this, we first create a backup of the initial `m` elements of `nums1`.

1.  **Create a Copy**: Make a copy of the first `m` elements of `nums1` into a new array, say `nums1_copy`.
2.  **Initialize Pointers**: Use three pointers: `p1` to traverse `nums1_copy`, `p2` to traverse `nums2`, and `p` to write into `nums1`.
3.  **Merge**: Compare elements at `nums1_copy[p1]` and `nums2[p2]`. The smaller of the two is placed at `nums1[p]`. The corresponding pointers (`p1` or `p2`, and `p`) are then incremented.
4.  **Copy Remainder**: Once one of the arrays is exhausted, the remaining elements from the other array are copied over to the end of `nums1`.

```java
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // Make a copy of the first m elements of nums1.
        int[] nums1_copy = new int[m];
        System.arraycopy(nums1, 0, nums1_copy, 0, m);

        // Pointers for nums1_copy, nums2, and the main nums1 array.
        int p1 = 0;
        int p2 = 0;
        int p = 0;

        // Compare elements from nums1_copy and nums2 and write the smaller one into nums1.
        while (p1 < m && p2 < n) {
            if (nums1_copy[p1] <= nums2[p2]) {
                nums1[p++] = nums1_copy[p1++];
            } else {
                nums1[p++] = nums2[p2++];
            }
        }

        // If there are remaining elements in nums1_copy, copy them.
        while (p1 < m) {
            nums1[p++] = nums1_copy[p1++];
        }

        // If there are remaining elements in nums2, copy them.
        while (p2 < n) {
            nums1[p++] = nums2[p2++];
        }
    }
}
```
### Algorithm
*   Create a copy of the first `m` elements of `nums1`, let's call it `nums1_copy`.
*   Initialize three pointers: `p1` for `nums1_copy` (starts at 0), `p2` for `nums2` (starts at 0), and `p` for `nums1` (starts at 0).
*   While `p1 < m` and `p2 < n`:
    *   Compare `nums1_copy[p1]` and `nums2[p2]`.
    *   Place the smaller element into `nums1[p]`.
    *   Increment the pointer of the array from which the element was taken (`p1` or `p2`).
    *   Increment `p`.
*   After the main loop, one of the arrays might have remaining elements.
*   If `p1 < m`, copy the rest of `nums1_copy` into `nums1`.
*   If `p2 < n`, copy the rest of `nums2` into `nums1`.

## In-place Merge from End (Three Pointers)
The optimal solution achieves linear time complexity with constant extra space. The key insight is to fill the `nums1` array from the end towards the beginning. Since the last `n` elements of `nums1` are empty (placeholders), we can place the largest elements of the merged array there without overwriting any data we still need to inspect. This avoids the need for an auxiliary array.
**Time:** O(m+n) · **Space:** O(1)
**Pros:** Optimal time complexity of O(m+n).; Optimal space complexity of O(1) as it performs the merge in-place.; Elegant solution that cleverly uses the available space.
**Cons:** Can be slightly less intuitive to come up with compared to the auxiliary array approach.
### Explanation
This approach cleverly utilizes the available space at the end of `nums1` to perform the merge in-place without needing an auxiliary array. By filling the merged array from the end, we ensure that we never overwrite a value in `nums1` that we haven't processed yet.

1.  **Initialize Pointers**: Set up three pointers. `p1` points to the last valid element of `nums1` (`m-1`), `p2` points to the last element of `nums2` (`n-1`), and `p` (the write pointer) points to the last index of `nums1` (`m+n-1`).
2.  **Merge from End**: In a loop, compare the elements at `nums1[p1]` and `nums2[p2]`. The larger element is placed at `nums1[p]`. The pointer corresponding to the larger element is decremented, and the write pointer `p` is also decremented.
3.  **Handle Remaining `nums2` Elements**: The loop continues until one of the pointers (`p1` or `p2`) goes below 0. If `p2` is still non-negative, it means there are elements left in `nums2` that are smaller than all the processed elements. These remaining `nums2` elements are copied into the remaining empty slots at the beginning of `nums1`.
4.  **No Action for `nums1`**: If `p1` is still non-negative, the elements it points to are already in their correct final positions, so no further action is needed.

```java
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // Pointer for the last element of the initial part of nums1
        int p1 = m - 1;
        // Pointer for the last element of nums2
        int p2 = n - 1;
        // Pointer for the last position in nums1
        int p = m + n - 1;

        // Iterate from the end of both arrays
        while (p1 >= 0 && p2 >= 0) {
            // Place the larger element at the end of nums1
            if (nums1[p1] > nums2[p2]) {
                nums1[p] = nums1[p1];
                p1--;
            } else {
                nums1[p] = nums2[p2];
                p2--;
            }
            p--;
        }

        // If there are remaining elements in nums2, copy them.
        while (p2 >= 0) {
            nums1[p] = nums2[p2];
            p2--;
            p--;
        }
    }
}
```
### Algorithm
*   Initialize three pointers:
    *   `p1` pointing to the last valid element in `nums1` (`m - 1`).
    *   `p2` pointing to the last element in `nums2` (`n - 1`).
    *   `p` pointing to the very end of `nums1` (`m + n - 1`).
*   Loop backwards from the end of the arrays as long as there are elements to compare in both (`p1 >= 0` and `p2 >= 0`).
*   In each iteration, compare `nums1[p1]` and `nums2[p2]`.
*   Copy the larger of the two elements to `nums1[p]`.
*   Decrement the pointer of the array from which the element was taken (`p1` or `p2`).
*   Decrement the write pointer `p`.
*   After the loop, copy any remaining elements from `nums2` to the beginning of `nums1`. (No need to handle remaining `nums1` elements as they are already in place).

# Solutions
### Java

```java
class Solution {
public
  void merge(int[] nums1, int m, int[] nums2, int n) {
    for (int i = m - 1, j = n - 1, k = m + n - 1; j >= 0; --k) {
      nums1[k] = i >= 0 && nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
    }
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums1 * @param {number} m * @param {number[]} nums2 * @param {number} n * @return {void} Do not return anything, modify nums1 in-place instead. */ var merge =
  function (nums1, m, nums2, n) {
    for (let i = m - 1, j = n - 1, k = m + n - 1; j >= 0; --k) {
      nums1[k] = i >= 0 && nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
    }
  };

```

### CPP

```cpp
class Solution {
public:
  void merge(vector<int> &nums1, int m, vector<int> &nums2, int n) {
    for (int i = m - 1, j = n - 1, k = m + n - 1; ~j; --k) {
      nums1[k] = i >= 0 && nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
    }
  }
};

```

### Python

```python
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: """ Do not return anything, modify nums1 in-place instead. """ i, j, k = m - 1, n - 1, m + n - 1  # what if j=-1 already but k is not 0 yet? e.g. m=[1,2,0], n=[3] # => then no more ops needed, rest of m[] already sorted, so this while is good enough while j >= 0 : # i could be -1, eg. [7,8,9, ] and [1] if i >= 0 and nums1 [ i ] > nums2 [ j ]: nums1 [ k ] = nums1 [ i ] i -= 1 else : nums1 [ k ] = nums2 [ j ] j -= 1 k -= 1

```