The Divide-and-Conquer Strategy
What you'll learn: How mergesort breaks down an array into single elements before building the sorted result back up.
The Core Idea
Divide-and-conquer is a problem-solving approach where you break a large problem into smaller, more manageable pieces, solve each piece independently, and then combine the solutions. In mergesort, this means:
- Divide: Split the array into two halves
- Conquer: Recursively sort each half
- Combine: Merge the two sorted halves together
Breaking Down to Base Cases
The "divide" phase continues recursively until you reach the simplest possible case: an array with just one element. A single-element array is already sorted by definition—there's nothing to arrange!
Think of it like organizing a messy deck of cards. Instead of trying to sort all 52 cards at once, you split the deck in half, then split each half again, and again, until you're holding individual cards. Each single card is "sorted." Now you can start combining pairs of cards in order, then combining those pairs, and so on, until the entire deck is organized.
The Recursive Pattern
For an array of size n:
- First split: 2 subarrays of size
n/2 - Second split: 4 subarrays of size
n/4 - Continue splitting until you have
nsubarrays of size1
Once you hit these base cases (single elements), the recursion stops diving deeper and begins the "combine" phase—merging sorted pieces back together.
Key Takeaway: Divide-and-conquer in mergesort recursively splits an array into halves until reaching base cases of single elements, which are trivially sorted and ready to be merged back together.