Merge Sorted Arrays
Learn how to merge two sorted arrays into one sorted array in Python using the two-pointer technique.
Merge Sorted Arrays
Problem
Given two sorted arrays, merge them into one sorted array. Do not use Python's built-in sort() on the combined list — the goal is to take advantage of the fact that both arrays are already sorted.
Input: [1, 3, 5, 7], [2, 4, 6, 8]
Output: [1, 2, 3, 4, 5, 6, 7, 8]
Input: [1, 2, 3], [4, 5, 6]
Output: [1, 2, 3, 4, 5, 6]
Input: [4, 5, 6], [1, 2, 3]
Output: [1, 2, 3, 4, 5, 6]
Input: [1, 3, 5], [2, 2, 4]
Output: [1, 2, 2, 3, 4, 5]
Input: [], [1, 2, 3]
Output: [1, 2, 3]Logic
Two-pointer technique:
Both arrays are already sorted. Instead of combining and sorting, compare the front of each array and always take the smaller one.
- Start with a pointer at the beginning of each array —
i=0for arr1,j=0for arr2 - Compare
arr1[i]andarr2[j] - Take the smaller one — add it to result, advance that pointer
- Repeat until one array is exhausted
- Add all remaining elements from the other array
Flow
Solution 1 — two pointers
The most efficient approach. Compares elements from both arrays in one pass.
def merge_sorted(arr1, arr2):
result = []
i = 0 # pointer for arr1
j = 0 # pointer for arr2
# compare elements from both arrays
# always pick the smaller one
while i < len(arr1) and j < len(arr2):
if arr1[i] <= arr2[j]:
result.append(arr1[i])
i += 1 # move arr1 pointer forward
else:
result.append(arr2[j])
j += 1 # move arr2 pointer forward
# one array is exhausted — add remaining elements from the other
# at most one of these while loops will run
while i < len(arr1):
result.append(arr1[i])
i += 1
while j < len(arr2):
result.append(arr2[j])
j += 1
return result
print(merge_sorted([1, 3, 5, 7], [2, 4, 6, 8])) # [1, 2, 3, 4, 5, 6, 7, 8]
print(merge_sorted([1, 2, 3], [4, 5, 6])) # [1, 2, 3, 4, 5, 6]
print(merge_sorted([4, 5, 6], [1, 2, 3])) # [1, 2, 3, 4, 5, 6]
print(merge_sorted([1, 3, 5], [2, 2, 4])) # [1, 2, 2, 3, 4, 5]
print(merge_sorted([], [1, 2, 3])) # [1, 2, 3]
print(merge_sorted([1, 2, 3], [])) # [1, 2, 3]Code Execution — Solution 1
Trace through merge_sorted([1, 3, 5, 7], [2, 4, 6, 8]):
| Step | i | j | arr1[i] | arr2[j] | Compare | result |
|---|---|---|---|---|---|---|
| 1st | 0 | 0 | 1 | 2 | 1 <= 2 → take 1, i++ | [1] |
| 2nd | 1 | 0 | 3 | 2 | 3 > 2 → take 2, j++ | [1, 2] |
| 3rd | 1 | 1 | 3 | 4 | 3 <= 4 → take 3, i++ | [1, 2, 3] |
| 4th | 2 | 1 | 5 | 4 | 5 > 4 → take 4, j++ | [1, 2, 3, 4] |
| 5th | 2 | 2 | 5 | 6 | 5 <= 6 → take 5, i++ | [1, 2, 3, 4, 5] |
| 6th | 3 | 2 | 7 | 6 | 7 > 6 → take 6, j++ | [1, 2, 3, 4, 5, 6] |
| 7th | 3 | 3 | 7 | 8 | 7 <= 8 → take 7, i++ | [1, 2, 3, 4, 5, 6, 7] |
| 8th | 4 | 3 | — | 8 | i >= len(arr1) → stop | |
| Remaining | — | 3 | — | 8 | Add rest of arr2 | [1, 2, 3, 4, 5, 6, 7, 8] |
Trace through merge_sorted([4, 5, 6], [1, 2, 3]):
| Step | i | j | arr1[i] | arr2[j] | Compare | result |
|---|---|---|---|---|---|---|
| 1st | 0 | 0 | 4 | 1 | 4 > 1 → take 1, j++ | [1] |
| 2nd | 0 | 1 | 4 | 2 | 4 > 2 → take 2, j++ | [1, 2] |
| 3rd | 0 | 2 | 4 | 3 | 4 > 3 → take 3, j++ | [1, 2, 3] |
| 4th | 0 | 3 | 4 | — | j >= len(arr2) → stop | |
| Remaining | 0 | — | 4,5,6 | — | Add rest of arr1 | [1, 2, 3, 4, 5, 6] |
Using <= instead of < when comparing equal elements ensures stability — equal elements from arr1 come before equal elements from arr2. This preserves the relative order of equal values, which matters in many sorting algorithms.
Solution 2 — using slicing to add remaining elements
Same logic but use slice notation instead of a second while loop to add remaining elements.
def merge_sorted(arr1, arr2):
result = []
i = 0
j = 0
while i < len(arr1) and j < len(arr2):
if arr1[i] <= arr2[j]:
result.append(arr1[i])
i += 1
else:
result.append(arr2[j])
j += 1
# extend with remaining elements using slice
result.extend(arr1[i:]) # arr1[i:] is everything from i to end
result.extend(arr2[j:]) # one of these will be empty — that is fine
return result
print(merge_sorted([1, 3, 5, 7], [2, 4, 6, 8])) # [1, 2, 3, 4, 5, 6, 7, 8]
print(merge_sorted([1, 2, 3], [4, 5, 6])) # [1, 2, 3, 4, 5, 6]
print(merge_sorted([], [1, 2, 3])) # [1, 2, 3]Code Execution — Solution 2
Trace through merge_sorted([1, 2, 3], [4, 5, 6]):
| Step | i | j | arr1[i] | arr2[j] | Compare | result |
|---|---|---|---|---|---|---|
| 1st | 0 | 0 | 1 | 4 | 1 <= 4 → take 1 | [1] |
| 2nd | 1 | 0 | 2 | 4 | 2 <= 4 → take 2 | [1, 2] |
| 3rd | 2 | 0 | 3 | 4 | 3 <= 4 → take 3 | [1, 2, 3] |
| Stop | 3 | 0 | — | — | i >= len(arr1) |
result.extend(arr1[3:]) → arr1[3:] = [] → nothing added
result.extend(arr2[0:]) → arr2[0:] = [4, 5, 6] → added
Final: [1, 2, 3, 4, 5, 6]
Solution 3 — recursive approach
Recursively take the smaller front element from either array.
def merge_sorted(arr1, arr2):
# base cases — one array is empty
if not arr1:
return arr2
if not arr2:
return arr1
# take the smaller front element
# then recursively merge the rest
if arr1[0] <= arr2[0]:
return [arr1[0]] + merge_sorted(arr1[1:], arr2)
else:
return [arr2[0]] + merge_sorted(arr1, arr2[1:])
print(merge_sorted([1, 3, 5], [2, 4, 6])) # [1, 2, 3, 4, 5, 6]
print(merge_sorted([1, 2, 3], [4, 5, 6])) # [1, 2, 3, 4, 5, 6]
print(merge_sorted([], [1, 2, 3])) # [1, 2, 3]Code Execution — Solution 3
Trace through merge_sorted([1, 3], [2, 4]):
merge_sorted([1, 3], [2, 4])
1 <= 2 → [1] + merge_sorted([3], [2, 4])
3 > 2 → [2] + merge_sorted([3], [4])
3 <= 4 → [3] + merge_sorted([], [4])
arr1 empty → return [4]
return [3, 4]
return [2, 3, 4]
return [1, 2, 3, 4]The recursive solution creates many new lists with [arr1[0]] + merge_sorted(...). Each + creates a new list — O(n) memory at each level, O(n²) total. The two-pointer approach uses O(n) memory total. Use recursion for understanding — use two pointers in production.
Solution 4 — merge N sorted arrays
Extend the concept to merge any number of sorted arrays.
import heapq
def merge_n_sorted(arrays):
"""
Merge any number of sorted arrays efficiently.
Uses a min-heap to always pick the smallest current element.
"""
result = []
# heap stores (value, array_index, element_index)
heap = []
# push the first element of each array into the heap
for i, arr in enumerate(arrays):
if arr:
heapq.heappush(heap, (arr[0], i, 0))
while heap:
value, arr_idx, elem_idx = heapq.heappop(heap)
result.append(value)
# push the next element from the same array
next_idx = elem_idx + 1
if next_idx < len(arrays[arr_idx]):
heapq.heappush(heap, (arrays[arr_idx][next_idx], arr_idx, next_idx))
return result
arrays = [
[1, 4, 7],
[2, 5, 8],
[3, 6, 9]
]
print(merge_n_sorted(arrays))
# [1, 2, 3, 4, 5, 6, 7, 8, 9]
arrays2 = [
[1, 10, 20],
[2, 5, 15],
[3, 7, 25],
[4, 8, 30]
]
print(merge_n_sorted(arrays2))
# [1, 2, 3, 4, 5, 7, 8, 10, 15, 20, 25, 30]Code Execution — Solution 4
Trace through merge_n_sorted([[1, 4], [2, 5], [3, 6]]):
Initial heap (min-heap by first value):
[(1, 0, 0), (2, 1, 0), (3, 2, 0)]
| Pop | value | arr_idx | Push next | result | Heap |
|---|---|---|---|---|---|
| 1st | 1 | 0 | (4, 0, 1) | [1] | [(2,1,0),(3,2,0),(4,0,1)] |
| 2nd | 2 | 1 | (5, 1, 1) | [1,2] | [(3,2,0),(4,0,1),(5,1,1)] |
| 3rd | 3 | 2 | (6, 2, 1) | [1,2,3] | [(4,0,1),(5,1,1),(6,2,1)] |
| 4th | 4 | 0 | none | [1,2,3,4] | [(5,1,1),(6,2,1)] |
| 5th | 5 | 1 | none | [1,2,3,4,5] | [(6,2,1)] |
| 6th | 6 | 2 | none | [1,2,3,4,5,6] | [] |
Performance comparison
| Solution | Time | Space | Notes |
|---|---|---|---|
| Solution 1 — two pointers | O(n+m) | O(n+m) | Best for two arrays |
| Solution 2 — two pointers + extend | O(n+m) | O(n+m) | Same, slightly cleaner |
| Solution 3 — recursion | O(n+m) | O(n²) | Avoid for large arrays |
| Solution 4 — heap for N arrays | O(N log k) | O(k) | Best for multiple arrays |
Where n and m are lengths of the two arrays, N is total elements, k is number of arrays.
Which solution to use?
| Solution | How | Best when |
|---|---|---|
| Solution 1 | Two pointers | Default — merging two arrays |
| Solution 2 | Two pointers + extend | Slightly cleaner version of 1 |
| Solution 3 | Recursion | Understanding the concept |
| Solution 4 | Heap | Merging many sorted arrays |
Output
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 2, 3, 4, 5]
[1, 2, 3]
[1, 2, 3]