Problem statement

You are given two integer arrays nums1 and nums2, both sorted in non-decreasing order. Merge them into a single array sorted in non-decreasing order and return it.

Example 1

Input: nums1 = [1,2,3], nums2 = [2,5,6]
Output: [1,2,2,3,5,6]

Example 2

Input: nums1 = [1], nums2 = []
Output: [1]

Constraints

• 0 <= nums1.length, nums2.length <= 30
• -100 <= values <= 100
• Both inputs are sorted.

Hints for Merge Sorted Array

1. Hint 1

   Walk both arrays with one pointer each, always taking the smaller front element.

2. Hint 2

   When one array runs out, append the rest of the other.

How to solve Merge Sorted Array

Both inputs are already sorted, so the smallest unplaced value is always at the front of one of them. Walk the two arrays with a pointer each, repeatedly taking the smaller front element — the classic merge step from merge sort.

Approach

1. Start a pointer at the beginning of each array and an empty output.
2. While both still have elements, append the smaller front value and advance that pointer.
3. When one array is exhausted, append everything remaining in the other.
4. The output is sorted.

Why it works

The invariant is that everything already emitted is no greater than anything still unread: within each array that holds by sortedness, and across the two it holds because the comparison always takes the smaller front. So the output comes out in non-decreasing order and each element is copied exactly once, giving linear time — better than concatenating and re-sorting at O(n log n).

Complexity

• Time — O(n + m)
• Space — O(n + m) for the output

Pitfalls

• Drain the remaining array after the main loop; dropping it silently truncates the result.
• Either input may be empty, including both.
• Taking the left element on ties keeps the merge stable, which costs nothing.
• Advance only the pointer whose element you consumed.

Reference solution

Python

from typing import List

def merge(nums1: List[int], nums2: List[int]) -> List[int]:
    out = []
    i = j = 0
    while i < len(nums1) and j < len(nums2):
        if nums1[i] <= nums2[j]:
            out.append(nums1[i]); i += 1
        else:
            out.append(nums2[j]); j += 1
    out.extend(nums1[i:])
    out.extend(nums2[j:])
    return out

Java

public static int[] merge(int[] nums1, int[] nums2) {
    int[] out = new int[nums1.length + nums2.length];
    int i = 0, j = 0, p = 0;
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] <= nums2[j]) out[p++] = nums1[i++];
        else out[p++] = nums2[j++];
    }
    while (i < nums1.length) out[p++] = nums1[i++];
    while (j < nums2.length) out[p++] = nums2[j++];
    return out;
}

C++

vector<int> merge(vector<int>& nums1, vector<int>& nums2) {
    vector<int> out;
    size_t i = 0, j = 0;
    while (i < nums1.size() && j < nums2.size()) {
        if (nums1[i] <= nums2[j]) out.push_back(nums1[i++]);
        else out.push_back(nums2[j++]);
    }
    while (i < nums1.size()) out.push_back(nums1[i++]);
    while (j < nums2.size()) out.push_back(nums2[j++]);
    return out;
}

JavaScript

var merge = function(nums1, nums2) {
    const out = [];
    let i = 0, j = 0;
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] <= nums2[j]) out.push(nums1[i++]);
        else out.push(nums2[j++]);
    }
    while (i < nums1.length) out.push(nums1[i++]);
    while (j < nums2.length) out.push(nums2[j++]);
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Range Sum Query - Immutable Easy