# Solution: Merge Sorted Array

Let's solve the Merge Sorted Array problem using the K-way Merge pattern.

## 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

Since we have two sorted arrays to merge, this problem is the simplest illustration of the k-way merge pattern.

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.

We can solve this problem by comparing both arrays from the end and populating the result in the `nums1`

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

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.