Merge two sorted runs

Why it matters

Databases and log processors regularly combine streams that are already ordered. Sorting their union again wastes that structure, while allocating a third collection can double peak memory. Given nums1 = [1, 2, 3, 0, 0, 0] and nums2 = [2, 5, 6], fill nums1 in linear time with O(1) extra space without overwriting unread values.

nums1 has length m + n with the first m entries sorted and the rest 0. Merge sorted nums2 (length n) into nums1 in place and return it.

Input

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

Output

[1, 2, 2, 3, 5, 6]

In nums1 = [1, 2, 3, 0, 0, 0] and nums2 = [2, 5, 6], compare 3 with 6 and write 6 last. Filling the tail from right to left avoids copy-and-sort's O((m + n) log(m + n)) work and O(m + n) extra storage.

Start i on nums1's 3, j on nums2's 6, and write at nums1's last slot. Write 6, then compare 3 with 5 and write 5. Both writes land in empty tail slots, leaving every unread value safe.

Next write 3, then take nums2's 2 on the tie. nums2 is now exhausted, while nums1's original [1, 2] already occupies the correct first two slots. Filling from right to left ensures write never destroys a value that i still needs.