Bottom-Up Mergesort
What You'll Learn
You'll learn how to implement mergesort iteratively by merging progressively larger subarrays, eliminating recursion entirely.
The Core Idea
Bottom-Up Mergesort flips the traditional top-down approach on its head. Instead of recursively dividing the array into halves until you reach single elements, you start with single elements and iteratively merge them into larger sorted chunks.
Think of it like organizing books on a shelf: rather than dividing a huge pile recursively, you start by pairing up individual books, sorting each pair, then merging pairs into groups of four, then eights, and so on—doubling the size each pass until the entire shelf is sorted.
How It Works
- First pass: Treat each element as a sorted subarray of size 1. Merge adjacent pairs into sorted subarrays of size 2.
- Second pass: Merge adjacent sorted subarrays of size 2 into sorted subarrays of size 4.
- Third pass: Merge subarrays of size 4 into size 8.
- Continue doubling the subarray size until you've merged the entire array.
The algorithm uses a loop where the subarray size starts at 1 and doubles each iteration. In each iteration, you march through the array, merging adjacent subarrays of the current size using the same merge operation you learned earlier.
Why Use Bottom-Up?
- No recursion overhead: Avoids function call stack depth
- More control: Easier to optimize for specific scenarios
- Same complexity: Still O(n log n) time, O(n) space
- Predictable behavior: No risk of stack overflow on large inputs
Key Takeaway: Bottom-up mergesort achieves the same sorted result as recursive mergesort by iteratively merging subarrays of size 1, 2, 4, 8, etc., eliminating recursion while maintaining O(n log n) efficiency.