Merge two sorted arrays in-place

You are given two integer arrays sorted in non-decreasing order, and two integers m and n:

• nums1 has length m + n . The first m elements of nums1 contain valid numbers in sorted order. The last n elements of nums1 are placeholders (you can assume they are set to any values and should be ignored).
• nums2 has length n , and all n elements are valid and sorted in non-decreasing order.

Write an algorithm that merges the elements of nums2 into nums1 so that nums1 becomes a single sorted array containing all m + n elements, in-place (i.e., without using an additional array of size m + n).

Return value is not required; modify nums1 directly.

Example

Input:

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

After calling your function, nums1 should become:

• nums1 = [1, 2, 3, 4, 5, 6]

Constraints

• 0 <= m, n <= 10^5
• len(nums1) = m + n
• len(nums2) = n
• Arrays are already sorted in non-decreasing order.

Describe the algorithm and then implement it in the language of the interviewer's choice.