Link: https://leetcode.com/problems/merge-sorted-array/

Solution:

We know that both lists are already sorted, so we will use *m* and *n* as indexes to compare elements from right to left, therefore the initial *m–* and *n–*. We will use *m-1* as the initial **pivot** on *nums1* to start comparing *nums2* elements from right to left. If the *nums2* number is greater than the pivot we know that actually that number is the greatest from the both lists, so we can start swapping the zeros from right to left. But if its smaller than the pivot, we move the *pivot +1* on the right and the new number becomes the *new pivot*.

For the input: **nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3**

Iteration 1:

- Pivot: 3 (index 2)
- 3 < 6 replace: 0 from num1 with 6 from num2
- nums1: [ 1, 2, 3, 0, 0,
**6**]

Iteration 2:

- Pivot: 3 (index 2)
- 3 < 5 replace: 0 from num1 with 5 from num2
- nums1: [ 1, 2, 3, 0,
**5**, 6 ]

Iteration 3:

- Pivot: 3 (index 2)
- 3 > 2 replace: 0 from num1 with 3 from num1 (notice that this time the pivot goes +1 on the right)
- nums1: [ 1, 2, 3,
**3**, 5, 6 ]

Iteration 4:

- Pivot: 2 (index 1)
- 2 <= 2 replace: 3 from num1 with 2 from num2
- nums1: [ 1, 2,
**2**, 3, 5, 6 ]

```
var merge = function(nums1, m, nums2, n) {
if(n == 0) return;
var i = nums1.length-1;
m--;
n--;
while(n >= 0 && m >= 0)
{
if(nums1[m] > nums2[n])
nums1[i--]=nums1[m--];
else
nums1[i--]=nums2[n--];
}
if(n >= 0)
while(i >= 0)
nums1[i--]=nums2[n--];
if(m >= 0)
while(i >= 0)
nums1[i--]=nums1[m--];
};
```

Complexity: O(n)

## Leave a Reply