py_shadow_merge — Merge Two Sorted Lists

Difficulty: easy

Write a function that merges two sorted lists into one sorted list.

def shadow_merge(list1: list[int], list2: list[int]) -> list[int]:

Examples

>>> shadow_merge([1, 3, 5], [2, 4, 6])
[1, 2, 3, 4, 5, 6]

>>> shadow_merge([1, 2, 3], [4, 5, 6])
[1, 2, 3, 4, 5, 6]

>>> shadow_merge([1], [2, 3, 4])
[1, 2, 3, 4]

>>> shadow_merge([], [1, 2, 3])
[1, 2, 3]

>>> shadow_merge([1, 1, 2], [1, 3, 3])
[1, 1, 1, 2, 3, 3]

Solution

Download py_shadow_merge.py

def shadow_merge(list1: list[int], list2: list[int]) -> list[int]:
    result = []
    i = j = 0
    while i < len(list1) and j < len(list2):
        if list1[i] <= list2[j]:
            result.append(list1[i])
            i += 1
        else:
            result.append(list2[j])
            j += 1
    result.extend(list1[i:])
    result.extend(list2[j:])
    return result

How It Works

Goal: Combine two already-sorted lists into one fully sorted list in linear time.

Approach: Walk two pointers i and j through the inputs; at each step take the smaller front element and advance that pointer.

Step by step:

1. Use indices i and j starting at 0.
2. While both lists still have elements, compare list1[i] and list2[j] and take the smaller one.
3. Once one list is exhausted, append the remainder of the other (already sorted).
4. Return the assembled list.

Key concept: Two-pointer merge — the core step of merge sort. Because both inputs are sorted, you never need to look beyond the current front element of each.