Foundation · Module 6 · Lesson 3
Merge pointers
Walk two sorted sequences in linear time.
15–25 min readLesson 34 of 123
Lesson 34 of 123
1d streakTheory lesson · Step-by-step
Understand Merge pointers
Walk two sorted sequences in linear time.
Worked approach
Trace the reasoning step by step
- 1Assign a precise meaning to both pointers in Merge pointers.
- 2Use ordering or a read/write contract to decide which pointer can move safely.
- 3Record a match or write a finalized value before moving past it.
- 4Move at least one pointer monotonically on every iteration.
- 5Test duplicates, crossing pointers, empty ranges, and all-equal values.
Concrete example
Merge [1,4,7] and [2,3,8].
- 1Take 1, then 2 and 3.
- 2Take 4 and 7.
- 3Append remaining 8.
Merged output is [1,2,3,4,7,8].
What must remain true (Loop Invariant)
The region discarded by Merge pointers cannot contain an unexamined valid answer; each pointer move is justified by order or a finalized output position.
Cost Model
Complexity & Trade-offs
OperationTimeSpaceWhy
Pointer scan
O(n)
O(1)
Sorting first changes the total to O(n log n) unless the input is already ordered.When to use it
- Sorted pair search, compaction, merging, partitioning, and palindrome checks.
- Replacing nested loops when boundaries move monotonically.
- Maintaining disjoint processed and candidate regions.
Common mistakes
- Moving a pointer without proving the discarded region is impossible.
- Forgetting duplicate skipping in enumeration problems.
- Applying an order-dependent pointer rule to unsorted data.
Practice prompts
- Reproduce the worked Merge pointers example without looking at the trace.
- Change one input condition and explain whether the Merge pointers invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check
Can you derive it instead of memorizing it?
State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.