Bottom-Up Merge Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Bottom-Up Merge Sort

Same merges, no recursion. Walk over the array in runs of size 1, then 2, then 4, doubling each pass until the whole array is one run.

How it works

The recursive Merge Sort splits then merges. Bottom-Up Merge Sort flips this around: it starts assuming runs of length 1 are already sorted, then merges adjacent runs into runs of length 2, then 4, and so on.

1. Start with run width w = 1.
2. Walk the array: merge each pair of adjacent runs of width w into one run of width 2w.
3. Double w and repeat until w ≥ n.

The total work and stability are identical to top-down Merge Sort. What changes: no recursion, no function-call stack, and slightly better cache behavior because passes are sequential. This formulation is preferred for external/disk-based merge sort.

Complexity

Interactive visualization

Pseudocode

procedure bottomUpMergeSort(A):
  n ← length(A)
  w ← 1
  while w < n:
    for lo from 0 to n − 1 step 2w:
      mid ← min(lo + w − 1, n − 1)
      hi  ← min(lo + 2w − 1, n − 1)
      merge(A, lo, mid, hi)
    w ← 2w

JavaScript implementation

function bottomUpMergeSort(arr) {
  const n = arr.length;
  for (let w = 1; w < n; w *= 2) {
    for (let lo = 0; lo < n; lo += 2 * w) {
      const m  = Math.min(lo + w - 1, n - 1);
      const hi = Math.min(lo + 2 * w - 1, n - 1);
      merge(arr, lo, m, hi);
    }
  }
  return arr;
}

function merge(arr, lo, m, hi) {
  const aux = arr.slice(lo, hi + 1);
  let i = 0, j = m - lo + 1, k = lo;
  while (i <= m - lo && j <= hi - lo) {
    if (aux[i] <= aux[j]) {
      arr[k] = aux[i]; i++;
    } else {
      arr[k] = aux[j]; j++;
    }
    k++;
  }
  while (i <= m - lo) { arr[k] = aux[i]; i++; k++; }
  while (j <= hi - lo) { arr[k] = aux[j]; j++; k++; }
}

Pros and cons

When to use it

• External merge sort on disk-resident data.
• Stack-limited environments (embedded, scripted languages with low recursion depth).
• Pipeline-friendly data processing systems.