Merge sorted array

nums1 has length m + n: its first m elements are sorted values and the last n are zeros to be overwritten. nums2 has n sorted values. Merge nums2 into nums1 so that nums1 ends up sorted.

Before you code

Merging from the front overwrites values of nums1 that haven't been compared yet. The free space is at the back, so fill it first.

Hints

1. Use three indexes: i = m - 1, j = n - 1, and write = m + n - 1.
2. While j >= 0, write the larger of nums1[i] and nums2[j] at write, and move that index and write back. Treat i < 0 as "nums1 is used up".
3. When nums2 is used up, the rest of nums1 is already in place.

Production & complexity notes

When solving Merge sorted array on LeetCode (easy), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Two pointers on arrays to reinforce the underlying pattern.

What it practices

One index per array, and choosing the direction that makes an in-place merge safe, from Two pointers on arrays.