Merge Two Sorted Lists Practice Problem
This data science coding problem helps you practice Sorting & Searching, merge two sorted lists, and implementation skills. Read the problem statement, write your solution, and strengthen your understanding of Sorting & Searching.
- Problem ID: 103
- Problem key: 103-merge-two-sorted-lists
- URL: https://datacrack.app/solve/103-merge-two-sorted-lists
- Difficulty: medium
- Topic: Sorting & Searching
- Module: Python Fundamentals
Problem Statement
# 🧩 Merge Two Sorted Lists
---
### 🎯 Goal
Merging two sorted sequences into one sorted sequence is the core operation of **merge sort** — one of the most efficient general-purpose sorting algorithms. It also appears in data pipelines when combining sorted chunks, in external sorting (sorting data too large for RAM), and in merge joins in databases.
---
### 🔍 The Two-Pointer Technique
Use two pointers, one for each list. Always take the smaller current element:
```
list1: [1, 3, 5] list2: [2, 4, 6]
i=0, j=0 → take 1 (list1)
i=1, j=0 → take 2 (list2)
i=1, j=1 → take 3 (list1)
...
```
---
### 💻 Task
Implement `merge_sorted(list1, list2)` using the two-pointer approach.
---
### 📥 Input
- `list1`: list of integers sorted ascending
- `list2`: list of integers sorted ascending
### 📤 Output
- A new sorted list containing all elements from both lists
---
### 🧩 Starter Code
```python
def merge_sorted(list1, list2):
"""
Merge two sorted lists into one sorted list.
Args:
list1 (list[int]): First sorted list
list2 (list[int]): Second sorted list
Returns:
list[int]: Merged sorted list
"""
result = []
i, j = 0, 0
while i < len(list1) and j < len(list2):
# 🧠 TODO: Compare list1[i] and list2[j]
# 🧠 TODO: Append the smaller one and advance its pointer
pass
# 🧠 TODO: Append any remaining elements from list1 or list2
return result
```
---
### 💡 Example
```python
merge_sorted([1, 3, 5, 7], [2, 4, 6, 8])
# Expected: [1, 2, 3, 4, 5, 6, 7, 8]
```Starter Code
def merge_sorted(list1, list2):
"""
Merge two sorted lists into one sorted list.
Args:
list1 (list[int]): First sorted list
list2 (list[int]): Second sorted list
Returns:
list[int]: Merged sorted list
"""
result = []
i, j = 0, 0
while i < len(list1) and j < len(list2):
# 🧠 TODO: Compare list1[i] and list2[j]
# 🧠 TODO: Append the smaller one and advance its pointer
pass
# 🧠 TODO: Append any remaining elements from list1 or list2
return result