Summary - Merge sort
- Algorithms course
- Intermediate
- Lesson 4/80
- 4 min
Implement merge sort and print the result.
Summary - Merge sort
Merge sort runs in three steps: split, recursively sort, merge. The base case is a single-element array.
Each level processes n elements, there are log n levels; total O(n log n). It is stable and uses extra O(n) memory.
It is a strong choice for large arrays and external sorting; on small arrays the extra memory may be a cost.
Practice Summary: merge sort
Write merge_sort(arr). Split, sort, merge. Print [1, 1, 2, 3, 4, 5, 9] with print(merge_sort([3, 1, 4, 1, 5, 9, 2])).
Starter code
def merge_sort(arr):
# Split, sort, mergeSample solution
def merge(left, right):
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
def merge_sort(arr):
# Split, sort, merge
if len(arr) <= 1:
return arr
mid = len(arr) // 2
return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))
print(merge_sort([3, 1, 4, 1, 5, 9, 2]))Expected output
[1, 1, 2, 3, 4, 5, 9]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Summary - Merge sort: match the terms
| Term | Meaning |
|---|---|
Split |
O(1) |
Merge |
O(n) |
Total |
O(n log n) |
Memory |
O(n) extra |
2 Stable condition
Question
if left[i] ____right[j]:
Answer
if left[i] <=right[j]:Explanation: <= is right.
3 What is the memory cost of merge sort?
- O(n) extra Correct answer
- O(log n)
- O(n^2)
- O(1)
Explanation: O(n) extra