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.

Goal

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.

♾️ Constraints

1. $\text{nums1.length} = m + n$
2. $\text{nums2.length} = n$
3. $0 \leq m, n \leq 200$
4. $1 \leq m + n \leq 200$
5. $-10^9 \leq \text{nums1}[i], \text{nums2}[j] \leq 10^9$

Examples

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.
 

Solution

impl Solution {
    pub fn merge(nums1: &mut Vec<i32>, m: i32, nums2: &mut Vec<i32>, n: i32) {
        let (mut m, mut n) = (m as usize, n as usize);
 
        while n > 0 {
            if m > 0 && 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;
            }
        }
    }
}

Explanation

Coming soon...