Merge Sorted Array

Merge Sorted Arrays

Let's tackle a problem where we need to merge two sorted arrays into one larger sorted array.

Problem Statement

We are given two integer arrays, nums1 and nums2, that are both sorted in non-decreasing order.

We are also given the number of elements in each array, m and n.

Our goal is to:

1. Merge the two arrays into a single array
2. Ensure the merged array is also sorted

The catch is that instead of creating a new array, we need to do the merge in-place into nums1.

nums1 has extra space at the end to fit all the elements. We should:

• Merge nums2 into the end of nums1
• Sort the final result in nums1

Example

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

Result: nums1 = [1, 2, 2, 3, 5, 6]

We merged the sorted arrays [1, 2, 3] and [2, 5, 6] into the sorted result [1, 2, 2, 3, 5, 6].

Constraints

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
  
• -109 <= nums1[i], nums2[j] <= 109