Solution: Merge Sorted Array

Statement

Given two sorted integer arrays, $nums1$ and $nums2$, and the number of data elements in each array, $m$ and $n$, implement a function that merges the second array into the first one. You have to modify $nums1$ in place.

Note: Assume that $nums1$ has a size equal to $m + n$, meaning it has enough space to hold additional elements from $nums2$.

Constraints:

• nums1.length $= m + n$
• nums2.length $= n$
• $0 \leq m, n \leq 200$
• $1 \leq m + n \leq 200$
• $-10^3 \leq$ nums1[i], nums2[j] $\leq 10^3$

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

The naive approach here is to append the second list to the first—at a cost of $O(n)$—and then sort it using quick sort—at a cost of $O((m + n) \log(m + n))$—for an overall time complexity of $O((m + n) \log(m + n))$.

Optimized approach using k-way merge

This approach uses backward traversal to merge two sorted arrays into the first array in place. Initially, two pointers are set to point at the last elements of both arrays. A third pointer is also positioned at the end of the first array, pointing to the empty location. It compares the elements at the first and second pointer and checks the larger among them. The larger one is placed at the location pointed by the third pointer. Then pointers are adjusted, decrementing the third one and moving the first or second pointer one step back depending on the larger element. This ensures that the smallest element among the compared elements can be further considered in the merging process. This backward merging continues until all elements of the second array have been placed into the first array, resulting in a fully merged, sorted array.

With the k-way merge approach, we iterate over our given arrays using two pointers and merge them in place. The time complexity for this is $O(m + n)$, which is more efficient than the $O((m + n) \log(m + n))$ complexity of the naive approach.

The slides below illustrate how we would like the algorithm to run: