Merge Two Sorted Lists
Merge two sorted lists into one sorted list.
Merging sorted lists is a cornerstone algorithm in computer science, forming the basis of merge sort and appearing in database operations, file merging, and stream processing. This exercise teaches you optimal merging strategies and pointer manipulation.
📚 Concepts & Theory
Merging two sorted lists into one sorted list is a fundamental algorithm used in merge sort and data processing. The key insight is that you can create a sorted result efficiently by comparing elements from both lists.
Understanding the Merge Algorithm:
Method 1: Simple Concatenation + Sorting
list1 = [1, 3, 5]
list2 = [2, 4, 6]
merged = sorted(list1 + list2) # [1, 2, 3, 4, 5, 6]
# Time: O(n log n)Method 2: Two-Pointer Merge (Optimal)
def merge_sorted(list1, list2):
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
# Add remaining elements
result.extend(list1[i:])
result.extend(list2[j:])
return result
# Time: O(n + m)Method 3: Using heapq.merge()
import heapq
merged = list(heapq.merge(list1, list2))The Two-Pointer Strategy:
- Start with pointers at the beginning of both lists
- Compare elements at both pointers
- Add the smaller element to result
- Move the corresponding pointer forward
- When one list is exhausted, append remaining elements
- Core component of merge sort
- Efficient: O(n + m) vs O(n log n) for sort after concatenation
- Demonstrates two-pointer technique
- Foundation for external sorting algorithms
🎯 Your Challenge
Write merge_sorted that merges two sorted lists.
📝 Starter Code
def merge_sorted(a, b):
pass
print(merge_sorted([1,3,5], [2,4,6]))- Use two pointers, one for each list
- Compare elements at both pointers
- Add the smaller element to your result
- Move the pointer of the list you took from
- When one list is empty, add all remaining elements from the other
Solution
def merge_sorted(a, b):
result = []
i = j = 0
while i < len(a) and j < len(b):
if a[i] <= b[j]:
result.append(a[i])
i += 1
else:
result.append(b[j])
j += 1
result.extend(a[i:])
result.extend(b[j:])
return result
print(merge_sorted([1,3,5], [2,4,6]))Explanation
This solution uses the two-pointer technique to merge two sorted lists efficiently. Two pointers (i and j) track positions in each list. At each step, we compare the current elements and append the smaller one to the result, advancing that pointer. When one list is exhausted, we extend the result with remaining elements from the other list using slicing. This preserves the sorted order while only making one pass through each list. Time complexity: O(n + m) where n and m are the list lengths. Space complexity: O(n + m) for the result list.
⚠️ Common Mistakes to Avoid
- Simply concatenating and sorting (less efficient O(n log n))
- Not handling lists of different lengths
- Forgetting to add remaining elements after one list is exhausted
- Using wrong comparison operators (> instead of <=)
- Not initializing pointers to 0