Merge Sort: Divide, Sort, Merge
Implement merge sort recursively, trace the divide-and-conquer tree, and explain why it guarantees O(n log n) in all cases.
Divide and Conquer Intuition
Merge sort is a classic divide-and-conquer algorithm: split the array in half, recursively sort each half, then merge the two sorted halves into one sorted result. The insight is that merging two sorted arrays is O(n) — far cheaper than sorting from scratch. This decomposition produces a recursion tree with log n levels, each requiring O(n) merge work, giving the optimal comparison-sort bound of O(n log n).
# High-level merge sort structure
def merge_sort(arr):
# Base case: 0 or 1 element already sorted
if len(arr) <= 1:
return arr
# Divide
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # sort left half
right = merge_sort(arr[mid:]) # sort right half
# Conquer (merge)
return merge(left, right)
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]The Merge Step Explained
Merging two sorted arrays: maintain two pointers, one for each half. Compare the front elements; copy the smaller one to the output and advance that pointer. When one half is exhausted, copy the remainder of the other half directly. This runs in O(n) time and O(n) space for the output array. The merge step is the algorithmic heart of merge sort — understand it deeply.
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= preserves stability
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# Append remaining elements
result.extend(left[i:])
result.extend(right[j:])
return result
print(merge([1,3,5,7], [2,4,6,8]))
# [1, 2, 3, 4, 5, 6, 7, 8]All lessons in this course
- Bubble Sort and Insertion Sort
- Merge Sort: Divide, Sort, Merge
- Quick Sort and Pivot Selection
- Non-Comparison Sorts and Python's sort()