Merge two sorted sequences

36 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Two sorted lists, 1, 2, 3 and 2, 5, 6, must become one sorted list. By hand you would put everything together and sort: 1, 2, 2, 3, 5, 6. Sorting six numbers is nothing, but sorting n + m numbers costs about (n + m) log(n + m) comparisons, and it throws away the fact that each list is already in order. There should be a way to use that order so the merge costs only one look per element.

Build the structure, one piece at a time

Piece one: a finger on the front of each list. The smallest unused number overall must be one of the two fingers, because everything behind a finger is larger than it. So the merge is: compare the two fingers, take the smaller, advance that finger, repeat. With 1, 2, 3 and 2, 5, 6: take 1, take 2 (from the first list, on ties take either), take 2, take 3, then the first list is empty, so copy the rest of the second: 5, 6.

Piece two, for the in-place version: the first array has spare room at its end, and the merge must happen inside it. Filling from the front would overwrite numbers in the first array that you have not yet read. So fill from the back: put a finger i on the last real value of the first array, j on the last value of the second, and k on the last empty slot. Compare, write the larger at k, move that finger and k left.

When the second list runs out first, the remaining first-list numbers are already in place, so there is nothing to do. When the first runs out, keep copying the second.

Why it is correct

The invariant for the front-to-back merge: the output is sorted and contains exactly the elements consumed so far, and every unconsumed element is at least as large as the last output. Taking the smaller finger keeps the last part true, because the other finger and everything behind both fingers are larger, by sortedness. So each appended element is at least the previous one, and the output stays sorted.

For the back-to-front version the extra claim is that no unread element is ever overwritten. Slot k is the last empty slot, and the number of empty slots to its left equals the number of elements remaining in the second list; the first array's unread elements sit at indices up to i, and

k = i + j + 1 ≥ i + 1

whenever j ≥ 0, so k is always strictly past i. The slot we write into was either empty or already read.

Why it is fast

Each comparison consumes one element from one list, so there are at most n + m comparisons and exactly n + m writes: O(n + m) time, O(1) extra memory in the in-place version. Compared with re-sorting, the log factor disappears because sortedness lets us know the next smallest element without searching.

How to recognise it in an interview

Cues: "two sorted …", "merge", "intersection of sorted arrays", "k sorted lists" (merge pairwise or with a heap), "in place with extra space at the end" (merge from the back). The first thing to say: "Both inputs are sorted, so I will walk them with one pointer each and always take the smaller head; if it must be in place I will fill from the back."

Merge Sorted Array is the example. Merge Two Sorted Lists is the front-to-back version on linked nodes, splicing instead of copying. Intersection of Two Arrays II is the same walk where equal heads are output and unequal heads advance the smaller one.

02The idea in one line

Compare heads, take the smaller, advance that side.

Reach for it when: Merge arrays/lists, intersections, merge from the back when space is in place.

Cost: O(n + m) time.

03The walk-through, step by step

The video works one example: Merge Sorted Array [1,2,3] + [2,5,6] from the back. These are its captions in order, so you can follow without the video or check a step you missed.

1. Fill from the back so nothing unread is overwritten
2. i and j sit on the last real values, k on the last empty slot
3. 6 ≥ 3: write nums2[2] = 6 at slot 5
4. 5 ≥ 3: write nums2[1] = 5 at slot 4
5. 3 > 2: write nums1[2] = 3 at slot 3
6. 2 ≥ 2: write nums2[0] = 2 at slot 2
7. nums2 is used up; whatever is left in nums1 is already in place
8. Every element is written once: O(n + m), in place

04Asked at Google

8 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Two Pointers: Opposite ends converge, Fix one, two-pointer the rest, Reader / writer pointers, Dutch national flag partition, Two-sided max walls.