This is the merge step from merge sort, with one constraint: we have to merge in-place into nums1, which already has extra space at the end to hold all elements from nums2.

Merging from the front, comparing the smallest elements first, runs into a problem. If nums2[0] is smaller than nums1[0], placing it at the front of nums1 overwrites a value we have not processed yet. Avoiding that means shifting elements right, which turns a linear operation into O(m \* n).

The back of nums1 is empty, filled with placeholder zeroes. Merging from the back instead, placing the largest elements first, writes into those empty slots and never overwrites a value we still need.

Key Constraints:

Intuition

Copy all elements from nums2 into the empty slots at the back of nums1, then sort the entire array. A built-in sort produces the final order without any merge logic.

This ignores the fact that both arrays are already sorted and treats the problem as a generic "combine and sort" task. That wasted information is why it is slower than necessary, but it is correct and short, which makes it a useful baseline.

Algorithm

Example Walkthrough

Code

The next approach uses the fact that both arrays are already sorted to merge them in a single linear pass, avoiding the re-sort entirely.

Intuition

Both arrays are sorted, so their largest elements sit at the ends, and the placeholder slots at the back of nums1 are exactly where the largest merged values belong. Start from the back of both arrays, compare the two largest unplaced elements, place the bigger one at the end of nums1, and move the pointers backward.

The write always lands in a slot that is either a placeholder or a nums1 element that has already been read. The next section justifies why that conflict-free property holds at every step.

Algorithm

Example Walkthrough

Code