Merge Sorted Array

Problem

You are given two integer arrays sorted in non-decreasing order. nums1 has length m + n: its first m entries are meaningful and the remaining n entries are zero placeholders reserved for the merge. nums2 has length n. Merge nums2 into nums1 so that nums1 ends up containing all m + n values in sorted order. Do the merge in place; do not return a new array.

• m and n are each at most 1,000, and at least one of them is positive.
• Values are integers between -1,000,000 and 1,000,000.
• Aim for O(m + n) time and O(1) extra space.

Examples

• nums1 = [3, 8, 11, 0, 0], m = 3, nums2 = [5, 9], n = 2 → nums1 becomes [3, 5, 8, 9, 11].
• nums1 = [7], m = 1, nums2 = [], n = 0 → nums1 stays [7].
• nums1 = [0, 0], m = 0, nums2 = [2, 4], n = 2 → nums1 becomes [2, 4]. Both placeholders are overwritten.

Hints

1. Merging front-to-back into nums1 overwrites values you have not read yet. Where in nums1 is there guaranteed free space?
2. The largest remaining value of the two arrays belongs at the last unfilled slot.
3. Three indices walking backward: the tail of nums1's real data, the tail of nums2, and the write position at the very end of nums1.