Merge Two Sorted Arrays

Problem Given two sorted arrays, merge them into a single sorted array. In the in-place variant, the first array already carries enough trailing capacity for both, and the merge must write directly into it.

Input / Output

• Input: nums1 holding m valid elements followed by n placeholder slots, and nums2 holding n elements. Both sorted ascending.
• Output: nums1 containing all m+n elements in sorted order; nothing is returned.

Constraints

• The arrays may differ in length, and either may be empty.
• In-place means O(1) extra space — no temporary buffer — which is precisely what makes the naive forward merge fail.
• Duplicate values across the two arrays are allowed and must all survive.

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] — the empty-first-array boundary.
• nums1 = [2,5,6,0,0,0], m=3, nums2 = [1,2,3], n=3 → [1,2,2,3,5,6]; nums2 is entirely smaller here, so the leftover-nums2 drain loop actually runs — the case that catches implementations that forget it.