In-Place Merge of Sorted Arrays

An Applied Materials process-monitoring routine receives two nondecreasing arrays of sensor readings. The first array, nums1, has enough trailing capacity to store every value from nums2. Merge both sorted arrays directly into nums1 without allocating another array and without using sorting or built-in merge methods.

nums1 contains m valid readings followed by n placeholder slots. nums2 contains n valid readings. Modify nums1 so its first m + n positions contain all readings in nondecreasing order, and return nums1.

Formal Specification

Implement merge_sorted_arrays(nums1, m, nums2, n).

• Input: integer list nums1 of length m + n, integer m, integer list nums2 of length n, and integer n.
• Output: the modified nums1 list.
• The first m elements of nums1 and all elements of nums2 are sorted in nondecreasing order.
• Do not allocate an auxiliary array or call sorting, merging, or equivalent built-in methods.