Shahrouz Nikseresht

Posted on Nov 28

Day 48: Python Merge Two Sorted Lists - Master the Two-Pointer Technique in Pure O(n)

#challenge #python #intermediate #programming

Welcome to Day 48 of the #80DaysOfChallenges journey! This intermediate challenge conquers the timeless merge two sorted lists problem, delivering a buttery-smooth, lightning-fast solution using the legendary two-pointer technique. No built-in sort(), no extra memory tricks, just pure linear-time merging that handles duplicates, uneven lengths, and empty lists like a champ. This exact pattern dominates interviews, LeetCode #21 (Merge Two Sorted Lists), and real-world data pipelines, and once you internalize it, you'll merge anything with total confidence.

Example:

[1, 3, 5] + [2, 4, 6] → [1, 2, 3, 4, 5, 6]

[1, 2, 4] + [1, 3, 4] → [1, 1, 2, 3, 4, 4]

If you're grinding coding interviews, building merge-sort from scratch, or simply crave that clean algorithmic high, this guide hands you the most intuitive and battle-tested two-pointer merge in Python.

💡 Key Takeaways from Day 48: Two-Pointer Merge Mastery

This challenge gifts you one elegant function that walks two indices forward, always picking the smaller head until one list is exhausted, then scoops up the rest. Let's break it down: pointer setup, comparison core, remnant cleanup, and interactive tester.

1. Function Setup: Initialize Pointers and Result

def merge_sorted_lists(list1: list[int], list2: list[int]) -> list[int]:
    """
    Merge two pre-sorted lists into one sorted list using two pointers.
    Returns a brand-new merged list, originals stay untouched.
    """
    i, j = 0, 0
    result = []

i tracks progress in list1, j tracks list2
result grows incrementally, keeping everything pure and immutable-friendly
Empty lists? Handled automatically, no special cases needed

2. The Core Merge Loop: Compare and Advance

    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

Pure beauty in motion:

Compare current heads, append the smaller one, move its pointer
<= gracefully handles duplicates (swap to < if you prefer list1 bias)
Each element is touched exactly once → guaranteed O(m + n) time

Example step-by-step with [1,3,5] and [2,4,6]:

1 < 2 → append 1, i=1
3 > 2 → append 2, j=1
3 < 4 → append 3, i=2
Continues until perfection

3. Drain the Survivors: Append Remaining Elements

    while i < len(list1):
        result.append(list1[i])
        i += 1

    while j < len(list2):
        result.append(list2[j])
        j += 1

    return result

After the main loop, at least one list is fully consumed
The two final loops pour in whatever is left (already sorted!)
Zero overhead, zero drama

4. Interactive Main: Instant Testing Power

print("Enter the first sorted list (space-separated integers):")
list1 = list(map(int, input().strip().split()))

print("Enter the second sorted list (space-separated integers):")
list2 = list(map(int, input().strip().split()))

merged = merge_sorted_lists(list1, list2)
print("Merged result:", merged)

Clean prompts, bulletproof parsing, immediate feedback. Try a dozen cases in seconds.

🎯 Summary and Reflections

This two-pointer merge is short, blindingly fast, and instantly readable. It drove home three eternal truths:

Two pointers turn O(n log n) problems into O(n) magic
Building results incrementally beats collecting + sorting every time
Remnant loops are your best friend for uneven inputs

I use this exact pattern in production ETL jobs, log merging, and interview whiteboards because it's impossible to mess up once you see it.

Advanced Alternatives:

heapq.merge(list1, list2) for lazy iteration or k-way merge
Linked-list version with dummy node (O(1) extra space)
In-place merge if one list has enough capacity (rare in Python)

But for everyday Python work? This classic two-pointer version wins on clarity, speed, and sheer satisfaction.

🚀 Next Steps and Resources

Day 48 cemented the two-pointer merge into muscle memory. Throw million-element lists at it. It still finishes before you blink!

Source Code for Challenge #48: scripts/merge_sorted_lists.py
Main Repository: 80-days-of-challenges
Daily Updates: Twitter/X (@Shahrouzlogs)

Tag your version with #80DaysOfChallenges. I read every single one! 🔥

DEV Community