Merge Two Unsorted Arrays into the First Array

Problem Statement

You are given two unsorted integer arrays, a and b, along with two integers m and n.

• m represents the number of valid elements in array a.
• n represents the number of elements in array b.
• Array a has a total length of m + n, where the first m positions contain valid elements and the remaining n positions are reserved placeholder values (which may be any arbitrary integer, such as 0 or garbage values).

Merge all elements of b into a so that a contains all m + n elements sorted in non-decreasing (ascending) order. The modification must be done in place in a without returning a new array.

Function Signature

def merge_and_sort(a: list[int], m: int, b: list[int], n: int) -> None:
    """
    Do not return anything, modify a in-place instead.
    """
    pass

Examples

Example 1

Input: a = [5, 1, 9, 0, 0, 0], m = 3, b = [8, 2, 4], n = 3
Output: [1, 2, 4, 5, 8, 9]
Explanation: The first 3 elements of a are [5, 1, 9]. We copy [8, 2, 4] into the remaining positions, yielding [5, 1, 9, 8, 2, 4], and then sort the combined array in place.

Example 2

Input: a = [3, -1, 0, 0], m = 2, b = [0, -5], n = 2
Output: [-5, -1, 0, 3]
Explanation: Note that 0 can be both a valid element and a placeholder value. Always rely on m and n rather than checking for 0.

Constraints

• len(a) == m + n
• len(b) == n
• 0 <= m, n <= 10^5
• 1 <= m + n <= 10^5
• -10^9 <= a[i], b[i] <= 10^9

Edge Cases to Consider

• m = 0: Array a consists entirely of placeholder values; copy all elements of b and sort them.
• n = 0: Array b is empty; a only needs to be sorted up to index m - 1.
• Arrays containing duplicate values or negative numbers.
• Placeholder values that overlap with valid numbers (e.g., zeros).