Merge Sorted Array

Concatenate + sort

The baseline ignores the inputs' sorted structure: join both arrays, then ask a general-purpose sort to order everything.

def merge(nums1: list[int], nums2: list[int]) -> list[int]:
    return sorted(nums1 + nums2)

It's compact and correct, but sorting makes comparisons that a true merge doesn't need.

Time O((m+n) log(m+n)) for m and n input values. Space O(m+n) for the returned array and the sorting work.

Merge from the back

Allocate the result once. Put i on the last value of nums1, j on the last value of nums2, and write on the result's last slot.

The larger of nums1[i] and nums2[j] is the largest value not yet written, so it belongs at result[write]. Move that source pointer and write left, then repeat. If one input runs out, the condition naturally takes values from the other.

def merge(nums1: list[int], nums2: list[int]) -> list[int]:
    merged = [0] * (len(nums1) + len(nums2))
    i = len(nums1) - 1
    j = len(nums2) - 1
    write = len(merged) - 1
 
    while write >= 0:
        if j < 0 or (i >= 0 and nums1[i] > nums2[j]):
            merged[write] = nums1[i]
            i -= 1
        else:
            merged[write] = nums2[j]
            j -= 1
        write -= 1
 
    return merged

Every comparison permanently places one value, so no work is repeated.

Time O(m+n) — every input value is written exactly once. Space O(m+n) for the required returned array, with O(1) extra space beyond that output.

LeetCode's version gives nums1 length m + n with trailing zero slots, mutates it in place, and returns void; ours receives only the real values and returns a new merged array.