Merge Sorted Array

Two sorted lists of numbers need to become one, but you're only allowed to write into the first list. It was allocated with exactly enough spare slots at the end to hold the second list.

Write merge_into(big: list[int], m: int, small: list[int], n: int) -> None.

• big has length m + n. Its first m values are sorted in non-decreasing order; the last n slots are placeholders (always 0) that you may overwrite.
• small has length n and is sorted in non-decreasing order.
• Rearrange big in place so that it holds all m + n values in non-decreasing order. Return nothing; the caller looks at big.

big = [2, 5, 9, 0, 0]
merge_into(big, 3, [1, 6], 2)
big   # [1, 2, 5, 6, 9]

big = [0, 0]
merge_into(big, 0, [-3, 4], 2)
big   # [-3, 4]

Constraints: 0 <= m, n <= 10^5, m + n >= 1; values are in [-10^9, 10^9].

Aim for O(m + n) time and O(1) extra space: no sorting, no copies of either list.