Merge Two Sorted Sequences
Walk both lists with one pointer each.
Merge Two Sorted Sequences is a free Coding Interview Prep lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
The Merge Step
Given two sorted lists, combine them into one sorted list. This merge is the heart of merge sort and shows up everywhere. 🔗
Two Inputs, One Pointer Each
Give each list its own pointer, both starting at index 0. You will walk them forward together, never backward.
i = 0
j = 0Always Take the Smaller
At each step compare the two fronts. Append the smaller one to the result, because it must come next in sorted order.
Advance the Winner
After you take a value, advance only the pointer it came from. The other list still has its smallest element waiting.
if a[i] <= b[j]:
out.append(a[i])
i += 1
else:
out.append(b[j])
j += 1The Main Loop
Keep merging while both lists still have elements. Once either runs out, the comparison no longer makes sense.
while i < len(a) and j < len(b):
# compare and append
passDrain the Leftovers
When one list empties, the other is already sorted, so just append its remaining tail straight onto the result.
out.extend(a[i:])
out.extend(b[j:])Why Tails Are Free
The leftover tail is already in order, so no more comparing is needed. One of those two extend calls simply adds nothing.
Linear Time Total
Every element is looked at once, so merging two lists of sizes n and m costs O(n + m) time. That is as fast as it gets.
Keep It Stable
Using <= when values tie keeps equal elements in their original order. That stability matters when you carry extra data.
Merge In Reverse Too
To merge into a buffer with no spare space, walk from the back instead, placing the largest element last. Same idea, mirrored.
From Merge to Sort
Split, sort halves, then merge: that recursion is merge sort. The two-pointer merge you just learned is its core engine.
Quick Check
You are merging two sorted lists with one pointer in each.
Recap
Walk two sorted lists with a pointer each, always taking the smaller front, then drain the tail. It runs in O(n + m) and powers merge sort. 🚀
Frequently asked questions
Is the “Merge Two Sorted Sequences” lesson free?
Yes — the full text of “Merge Two Sorted Sequences” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Merge Two Sorted Sequences”?
Walk both lists with one pointer each. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Merge Two Sorted Sequences” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Two Pointers on a Sorted Array
- Find a Pair with a Given Sum
- Remove Duplicates In Place
- Merge Two Sorted Sequences