Implementing Mergesort Recursively
What you'll learn: How to write the complete recursive mergesort function by combining the base case, recursive splitting, and merge operation.
Now that you understand divide-and-conquer and the merge operation, it's time to put them together into working code. Mergesort is a classic example of recursion because it breaks a problem into smaller identical problems.
The Structure
A recursive mergesort function has two essential parts:
Base Case: When the array has 0 or 1 elements, it's already sorted—just return it. This stops the recursion from going infinitely.
Recursive Case:
- Find the middle point to split the array in half
- Recursively sort the left half
- Recursively sort the right half
- Merge the two sorted halves together
Code Implementation
def mergesort(arr):
# Base case: arrays of length 0 or 1 are already sorted
if len(arr) <= 1:
return arr
# Recursive case: divide, conquer, combine
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
# Recursively sort both halves
sorted_left = mergesort(left_half)
sorted_right = mergesort(right_half)
# Merge the sorted halves
return merge(sorted_left, sorted_right)
Think of it like organizing a messy bookshelf: you split the books into two piles, ask friends to sort each pile (recursion), then merge the sorted piles back together in order.
The beauty is that each recursive call handles a smaller problem until you hit the base case—single elements that need no sorting.
Key Takeaway: Recursive mergesort consists of a base case (arrays of size ≤1) and a recursive case that splits, recursively sorts both halves, then merges them back together.