Python Program to Merge Two Sorted Lists
list(heapq.merge(a, b)) does exactly that.Merging sorted lists is the key step of merge sort, and it shows up whenever two ordered streams must be combined, such as two sorted lists of timestamps or prices. Because both inputs are already in order, you can build the result in a single pass instead of sorting everything again.
Below you will see the classic two-pointer algorithm, the built-in heapq.merge, and the simple sorted(a + b) that is often good enough. For related searching skills, see the binary search program.
| Input | Two lists sorted in ascending order |
|---|---|
| Output | One sorted list that contains every item from both |
| Approach | Two pointers: always take the smaller front item |
| Time complexity | O(n + m) for lists of length n and m |
Approach to merge sorted lists step by step
- Put a pointer
iat the start of listaandjat the start of listb. - Compare
a[i]andb[j]. Append the smaller one to the result and move that pointer forward. - Repeat while both lists still have items.
- When one list runs out, append everything left in the other list. It is already sorted, and every remaining item is at least as large as what you added.
Taking a[i] when the values are equal keeps the merge stable: equal items from a stay before those from b.
How the two-pointer merge code works
The while i < len(a) and j < len(b) loop runs only while both lists have unread items. Each pass adds one item, so the loop runs at most n + m times in total, and nothing is compared twice.
The lines result.extend(a[i:]) and result.extend(b[j:]) use slicing to copy whatever is left. At most one of them adds anything. Forgetting them is the most common bug in this program.
a, b = [1, 4, 9], [2, 3, 10, 11]
result, i, j = [], 0, 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:])
print(result)Other ways to merge sorted lists in Python
heapq.merge(a, b) returns a lazy iterator in sorted order, so wrap it in list(). It also accepts more than two lists. sorted(a + b) is the shortest code; Python's Timsort detects the two ordered runs, so it is fast in practice, but the two-pointer version is the one interviewers expect. Read more about sorting in Python and list.sort().
| Method | Time | Notes |
|---|---|---|
| Two pointers | O(n + m) | Shows the algorithm; the basis of merge sort |
heapq.merge(a, b) | O(n + m) for two lists | Lazy; works with many lists |
sorted(a + b) | O(n log n) in theory | Simplest; fast for already-sorted runs |
Examples you can run
Press Run, then edit the code and run it again.
Merge two sorted lists with two pointers
Always take the smaller front item, then append the leftovers.
def merge(a, b):
result, i, j = [], 0, 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([1, 4, 9], [2, 3, 10, 11]))Expected output[1, 2, 3, 4, 9, 10, 11]
Merge with heapq.merge and sorted()
Two shorter alternatives that give the same list.
import heapq
a = [1, 5, 8]
b = [2, 5, 9]
print(list(heapq.merge(a, b)))
print(sorted(a + b))Expected output[1, 2, 5, 5, 8, 9]
[1, 2, 5, 5, 8, 9]
Edge cases: empty lists and duplicates
An empty list leaves the other unchanged; duplicates are all kept.
def merge(a, b):
result, i, j = [], 0, 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
return result + a[i:] + b[j:]
print(merge([], [1, 2]))
print(merge([3, 3], [3]))
print(merge([], []))Expected output[1, 2]
[3, 3, 3]
[]
Interactive merge
Read two sorted lines of numbers and print the merged list.
import heapq
a = [int(x) for x in input("First: ").split()]
b = [int(x) for x in input("Second: ").split()]
print(list(heapq.merge(a, b)))Expected outputFirst: 1 3 5
Second: 2 4 6
[1, 2, 3, 4, 5, 6]
Common mistakes
Forgetting the leftover items
✗ Wrong
a, b = [1, 2], [5, 6, 7]
result, i, j = [], 0, 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
print(result)✓ Right
a, b = [1, 2], [5, 6, 7]
result, i, j = [], 0, 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:])
print(result)After the loop, extend the result with the remaining items of both lists.
Merging lists that are not sorted
✗ Wrong
import heapq
print(list(heapq.merge([5, 1], [4, 2])))✓ Right
print(sorted([5, 1] + [4, 2]))Sort each list first, or use sorted(a + b) when the inputs may be unordered.
Python Program to Merge Two Sorted Lists: questions people ask
How do I merge two sorted lists in Python?
Use list(heapq.merge(a, b)) or the two-pointer loop. For a quick solution, sorted(a + b) also returns a sorted list.
What is the time complexity of merging two sorted lists?
It is O(n + m), because each item of both lists is visited once. That is why merge sort is O(n log n) overall.
Is sorted(a + b) as good as a manual merge?
For most programs, yes. It is shorter and Python's sort is optimised for data that is already in ordered runs. Learn the manual merge to understand the algorithm behind merge sort.
Keep learning
Step-by-step lessons:
Python SortingPython ListsPython while Loops
Related:
Python Binary Search Program (Iterative and Recursive)Python List sort() MethodPython sorted() FunctionPython Bubble Sort Program (with Explanation)
More in list and dictionary programs:
Python Program to Find the Largest Number in a ListPython Program to Find the Second Largest Number in a ListPython Program to Calculate the Average of a ListPython Program to Flatten a Nested List of Any DepthPython Program to Transpose a Matrix See all →