Merge Two Sorted Arrays — The Easy Way First 🤝 10 XP Easy

Ctrl+Enter Run Ctrl+S Save

Coming up next is Merge Sorted Array (In-Place) — a classic LeetCode problem where you merge two sorted arrays without creating a new one. That's the hard version. Let's do the easy version first and build up to it! 🪜

Picture this: you have two stacks of student exams, both already sorted alphabetically. You need to combine them into one sorted pile. What do you do? You look at the top paper on each stack, pick the one that comes first alphabetically, put it in your new pile, and repeat. When one stack runs out, you dump the rest of the other stack on top. Done! 📚

That's exactly how merging two sorted arrays works. And it's also the merge step of Merge Sort — one of the most important algorithms in computer science!

The technique: Two Pointers

Pointer i starts at the beginning of arr1
Pointer j starts at the beginning of arr2
Compare arr1[i] vs arr2[j] — the smaller one goes into the result
Advance whichever pointer you picked from
When one array is exhausted, append all remaining elements from the other

Let's trace through merge_sorted([1, 3, 5], [2, 4, 6]):

# i=0, j=0: compare 1 vs 2 → pick 1, advance i  → result: [1]
# i=1, j=0: compare 3 vs 2 → pick 2, advance j  → result: [1, 2]
# i=1, j=1: compare 3 vs 4 → pick 3, advance i  → result: [1, 2, 3]
# i=2, j=1: compare 5 vs 4 → pick 4, advance j  → result: [1, 2, 3, 4]
# i=2, j=2: compare 5 vs 6 → pick 5, advance i  → result: [1, 2, 3, 4, 5]
# i=3 (done!), dump rest of arr2  →  result: [1, 2, 3, 4, 5, 6] ✅

Time complexity: O(n + m) where n and m are the lengths of the two arrays. We visit each element exactly once. No nested loops. No sorting needed (they're already sorted!). Beautiful. ✨

Space complexity: O(n + m) because we're creating a new result array. The in-place version (coming next!) brings this down to O(1) — but that's trickier. Walk before you run! 🏃

Edge case to think about: what if one array is empty? No problem — the loop won't run for the empty array, and you just return a copy of the other one. The extend at the end handles this automatically.

Once you nail this, you'll be ready for the in-place merge AND you'll already understand the core of Merge Sort. Two birds, one function! 🐦🐦

📋 Instructions

Write a function `merge_sorted(arr1, arr2)` that takes two **sorted** lists of integers and returns a **new sorted list** containing all elements from both. Use the two-pointer technique — do NOT just concatenate and sort (that defeats the purpose!). Print the results of all three test cases to match the expected output.

Use two pointers i and j, both starting at 0. While both arrays have elements left, compare arr1[i] and arr2[j] — append the smaller one and advance that pointer. After the loop, one array might still have leftovers — extend your result with the remaining slice using result.extend(arr1[i:]) and result.extend(arr2[j:]). 🎯

⚠️ Try solving it yourself first — you'll learn more!

def merge_sorted(arr1, arr2):
    result = []
    i, j = 0, 0
    while i < len(arr1) and j < len(arr2):
        if arr1[i] <= arr2[j]:
            result.append(arr1[i])
            i += 1
        else:
            result.append(arr2[j])
            j += 1
    result.extend(arr1[i:])
    result.extend(arr2[j:])
    return result

print(merge_sorted([1, 3, 5], [2, 4, 6]))
print(merge_sorted([1, 3, 5], [1, 2, 4]))
print(merge_sorted([1, 2, 3], []))

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›