Bottom-Up Merge Sort

Divide and Conquer

Recursively breaks the problem into smaller sub-problems, solves them, and combines the results.

Out-of-Place

Requires auxiliary memory proportional to the input size (O(n)).

Stable

Preserves the relative order of elements with equal values.

Bottom-up merge sort starts with runs of length one and repeatedly merges neighboring runs. It replaces recursion with passes of width 1, 2, 4, and so on.

Visualize Fullscreen

Demo

20 elements • 4x Speed

No Data

Did you know?

Every single item is already a sorted run, so this merge sort can start directly with pairs instead of recursive calls.
Its run widths double on each pass: 1, 2, 4, 8, and so on—even when the array length is not a power of two.
If the input length is odd or not a power of two, a final unpaired run can pass through a round unchanged. It is already sorted, so the next wider merge still works without padding the array.

How it Works

Treat every item as a sorted run of length one.
Merge adjacent runs into a temporary buffer, choosing the left item on ties.
Double run width after each full pass until one sorted run remains.

Complexity Analysis

Best Case

O(n \log n)

Average

O(n \log n)

Worst Case

O(n \log n)

Space

O(n)

Advantages

Stable and predictable O(n log n) work.
Avoids recursion depth.

Disadvantages

Needs O(n) working memory.

Implementation

JavaScript bottom-up-merge-sort.js

function bottomUpMergeSort(a) {
  for (let width = 1; width < a.length; width *= 2) {
    for (let start = 0; start < a.length; start += 2 * width) {
      const mid = Math.min(start + width, a.length);
      const end = Math.min(start + 2 * width, a.length);
      const left = a.slice(start, mid), right = a.slice(mid, end);
      let i = 0, j = 0, k = start;
      while (i < left.length || j < right.length)
        a[k++] = j === right.length ||
          (i < left.length && left[i] <= right[j]) ? left[i++] : right[j++];
    }
  }
  return a;
}