Merge Two Sorted Arrays In Place

Problem Given two sorted arrays nums1 and nums2, merge nums2 into nums1 so that nums1 becomes a single sorted array. nums1 has length m+n: its first m slots hold the real elements and the last n slots are zero-padding reserved for the merge. Do it in place.

Input / Output

• Input: nums1 (size m+n, first m valid) and m; nums2 (size n) and n.
• Output: nums1 mutated in place to the sorted merge of the two arrays.

Constraints

• 0 <= m, n <= 200; each input is individually sorted ascending.
• O(m+n) time, O(1) extra space.

Example

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