Course contentsShow
← Computer Science
Lesson 760 of 2,87218. Sorting AlgorithmsFree lesson

Bottom-Up Mergesort

Iterative implementation of mergesort that merges subarrays of increasing size without recursion.

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

  1. First pass: Treat each element as a sorted subarray of size 1. Merge adjacent pairs into sorted subarrays of size 2.
  2. Second pass: Merge adjacent sorted subarrays of size 2 into sorted subarrays of size 4.
  3. Third pass: Merge subarrays of size 4 into size 8.
  4. 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.