💡 [88] – Merge Sorted Arrays In-Place

This content originally appeared on DEV Community and was authored by Oybek Rejametov

Merge Sorted Arrays In-Place

Merging two sorted arrays is a classic problem that helps you practice array manipulation, pointers, and in-place updates.

Normally, you might create a new array to store the result. But what if you must merge in-place, without using extra space?

This is exactly what this problem asks.

You’re given:

• nums1, a sorted array of size m + n, where the first m elements are valid and the rest are 0 placeholders.
• nums2, a sorted array of size n.

Your task: merge nums2 into nums1, in-place, and keep the final result sorted.

Initial Arrays

nums1 = [1, 2, 3, 0, 0, 0]
nums2 = [2, 5, 6]

Pointers Initialization

i = 2   # Index of last non-zero element in nums1 (value: 3)
j = 2   # Index of last element in nums2 (value: 6)
k = 5   # Index of last position in nums1

We start comparing from the end and place the larger value at the end of nums1.

Step-by-Step Merge

Step 1

       i        k            j
[1, 2, 3, 0, 0, 0]    [2, 5, 6]

• Compare nums1[i] = 3 and nums2[j] = 6
• Since 6 > 3, place 6 at nums1[k]

Result:

nums1 = [1, 2, 3, 0, 0, 6]

Move pointers:

• j-- → 1 (move to next element in nums2)
• k-- → 4 (move to next empty spot in nums1)

Step 2

       i     k            j 
[1, 2, 3, 0, 0, 6]    [2, 5, 6]

• Compare nums1[i] = 3 and nums2[j] = 5
• Since 5 > 3, place 5 at nums1[k]

Result:

nums1 = [1, 2, 3, 0, 5, 6]

Move pointers:

• j-- → 0
• k-- → 3

Step 3

       i  k            j
[1, 2, 3, 0, 5, 6]    [2, 5, 6]

• Compare nums1[i] = 3 and nums2[j] = 2
• Since 3 > 2, place 3 at nums1[k]

Result:

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

Move pointers:

• i-- → 1
• k-- → 2

Step 4

    i  k               j
[1, 2, 3, 3, 5, 6]    [2, 5, 6]

• Compare nums1[i] = 2 and nums2[j] = 2
• Since 2 <= 2, place 2 from nums2 at nums1[k]

Result:

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

Move pointers:

• j-- → -1 (finished nums2)
• k-- → 1

Done!

nums2 is fully merged into nums1.

Final result:

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

Python Solution

def merge(nums1, m, nums2, n):
    i = m - 1         # last index of actual nums1 values
    j = n - 1         # last index of nums2
    k = m + n - 1     # last index of nums1 total space

    while j >= 0:
        if i >= 0 and nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1

This content originally appeared on DEV Community and was authored by Oybek Rejametov