Merge Sorted Array

EasyTwo pointersLeetCode 88 ↗World 1-15

0:00 / 0:00

Merge two sorted arrays into the first one in place: fill from the back, always placing the larger tail, so nothing gets overwritten.

▼

The problem

LeetCode 88 (Easy). nums1 has length m + n: its first m values are sorted, the last n slots are empty (zeros). nums2 holds n sorted values. Merge nums2 into nums1 in place so that nums1 is sorted. (Cousins in the series: ../merge-two-sorted-lists (zipper), ../merge-k-sorted-lists, ../median-of-two-sorted-arrays, ../sort-colors, ../remove-duplicates-from-sorted-array (library); this one has its own look.)

Examples (LeetCode's): nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 → [1,2,2,3,5,6] (walked through in scene 6); nums1 = [1], m = 1, nums2 = [], n = 0 → [1]; nums1 = [0], m = 0, nums2 = [1], n = 1 → [1].

TRY IT ON LEETCODE ▶

The solution

def merge(nums1, m, nums2, n):
    i, j, k = m - 1, n - 1, m + n - 1
    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

Transcript

Merge Sorted Array. Two sorted arrays. The first has m values, then n empty slots at the end, room for the second's n values. Merge the second into the first, in place, keeping it sorted.

One, two, three, with three empty slots, and two, five, six, give one, two, two, three, five, six. With nothing to add, one stays one. An empty first array takes the second: one.

The easy way: copy the second array into the gap, then sort. That's m plus n, times log of m plus n. Merging from the front is faster, but each write lands on a value you haven't read yet, unless you shift or copy.

So merge from the back, where the empty slots are. Point i at the first array's last value, j at the second's, and k at the last slot. Put the larger of the two at k, then step that pointer and k left. k stays ahead of i, so nothing unread is overwritten.

In code: set the three pointers, and loop while j has values. If the first array's value is larger, copy it; otherwise copy the second's. Then step k.

Let's walk it. Three against six: six goes last. Three against five: five. Three against two: three moves back. Two against two, a tie: take the second's two. j is done, so stop. One and two were already in place.

Each value moves at most once: order m plus n time, and order one extra space.

Fill from the back, take the larger, never overwrite. That's Merge Sorted Array.