Full merge sort
- Algorithms course
- Intermediate
- Lesson 3/80
- 4 min
Recursive merge sort with O(n log n) complexity.
Full merge sort
Full merge sort combines split + recursion + merge. Base case: if the array has one element, it is already sorted, return it.
Otherwise, split in two, recursively sort each half, then merge. Each call halves the problem.
The result: a stable sort that always runs in O(n log n).
Stability
Merge sort is stable: equal-key elements keep their relative order. This is because during merge, when left[i] <= right[j], we take the left element first.
Stability matters when sorting objects by a key: a secondary order is preserved.
That is why merge sort is preferred in database sorts and external sorting.
Practice Full merge sort
Write merge_sort(arr). Split, recursively sort, merge. Print [1, 2, 5, 8, 9] with print(merge_sort([5, 2, 8, 1, 9])).
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([5, 2, 8, 1, 9]))Expected output
[1, 2, 5, 8, 9]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Full merge sort: match the terms
| Term | Meaning |
|---|---|
Base case |
Single element |
Split |
Two halves |
Merging |
merge |
Cost |
O(n log n) |
2 When does merge sort give O(n log n)?
- Only in the best case
- Only on sorted arrays
- Only in the worst case
- Always Correct answer
Explanation: Always
3 Base case
if len(arr) ____1:if len(arr) <=1:Explanation: <= is right.