## Algorithm

Problem Name: 88. 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`.

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`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
void merge(int* nums1, int m, int* nums2, int n) {
int k = m + n - 1;
m --;
n --;
while (n >= 0) {
while (m >= 0 && nums1[m] > nums2[n]) {
nums1[k--] = nums1[m--];
}
nums1[k--] = nums2[n--];
}
}
``````
Copy The Code &

Input

cmd
nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3

Output

cmd
[1,2,2,3,5,6]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

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

// longer.
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i = m - 1, j = n - 1;
while(i + j + 1 >= 0){
nums1[i + j + 1] = i  <  0 ? nums2[j--] : j < 0 ? nums1[i--] : nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
}
}
};

``````
Copy The Code &

Input

cmd
nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3

Output

cmd
[1,2,2,3,5,6]

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int endIdxOne = m - 1;
int endIdxTwo = n - 1;
int currIdx = m + n - 1;
while (endIdxOne >= 0 || endIdxTwo >= 0) {
if (endIdxOne >= 0 && endIdxTwo >= 0) {
if (nums1[endIdxOne] > nums2[endIdxTwo]) {
nums1[currIdx--] = nums1[endIdxOne--];
} else {
nums1[currIdx--] = nums2[endIdxTwo--];
}
} else if (endIdxOne >= 0 && endIdxTwo  <  0) {
nums1[currIdx--] = nums1[endIdxOne--];
} else {
nums1[currIdx--] = nums2[endIdxTwo--];
}
}
}
}
``````
Copy The Code &

Input

cmd
nums1 = [1], m = 1, nums2 = [], n = 0

Output

cmd
[1]

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const merge = function(nums1, m, nums2, n) {
if (nums2.length === 0) return nums1;
let fi = 0;
let si = 0;
for (let i = si; i  <  n; i++) {
let se = nums2[i];
while (se >= nums1[fi] && fi  <  m + n && fi < m + i) {
fi++;
}
nums1.splice(fi, 0, se);
fi++;
}
while (nums1.length > m + n) {
nums1.pop();
}
};
``````
Copy The Code &

Input

cmd
nums1 = [1], m = 1, nums2 = [], n = 0

Output

cmd
[1]

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: void Do not return anything, modify nums1 in-place instead.
"""
while m > 0 and n > 0:
if nums1[m-1] >= nums2[n-1]:
nums1[m+n-1] = nums1[m-1]
m -= 1
else:
nums1[m+n-1] = nums2[n-1]
n -= 1
if n > 0:
nums1[:n] = nums2[:n]
``````
Copy The Code &

Input

cmd
nums1 = [0], m = 0, nums2 = [1], n = 1

Output

cmd
[1]

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _088_MergeSortedArray
{
public void Merge(int[] nums1, int m, int[] nums2, int n)
{
m--;
n--;
for (var i = m + n + 1; i >= 0; i--)
{
if (m >= 0 && n >= 0)
if (nums1[m] >= nums2[n]) nums1[i] = nums1[m--];
else nums1[i] = nums2[n--];
else if (n >= 0)
nums1[i] = nums2[n--];
}
}
}
}
``````
Copy The Code &

Input

cmd
nums1 = [0], m = 0, nums2 = [1], n = 1

Output

cmd
[1]