Merge operation
- Algorithms course
- Intermediate
- Lesson 2/80
- 4 min
Merge two sorted arrays into one sorted array.
Merge operation
Merge combines two sorted arrays into one sorted array. We place a pointer at the start of each, copy the smaller one to the result, and advance that pointer.
We continue until both arrays are exhausted. Each step copies one element; for n elements total work is O(n).
This step is the heart of merge sort: splitting is cheap, merging is the work.
Result array
During merging we keep an empty result list. Each step appends one element; at the end result holds the full sorted array.
Two more while loops handle leftovers: if either side still has elements, copy them all to the end. They are already sorted.
This leftover copy does not break the O(n) total.
Practice Merge two sorted arrays
Write merge(left, right). Merge two sorted arrays into a sorted result. Print [1, 2, 4, 5] with print(merge([1, 4], [2, 5])).
Starter code
def merge(left, right):
# Merge two sorted arraysSample solution
def merge(left, right):
# Merge two sorted arrays
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
print(merge([1, 4], [2, 5]))Expected output
[1, 2, 4, 5]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Comparison
if left[i] ____right[j]:if left[i] <=right[j]:Explanation: <= is right.
2 Merge operation: match the terms
| Term | Meaning |
|---|---|
Pointer |
Start |
Left array |
First half |
Leftover |
Copy to end |
Cost |
O(n) |
3 When is an element copied during merge?
- Never
- Only at the end
- When the smaller is found Correct answer
- At random
Explanation: When the smaller is found