Bottom Up Merge Sort

Bottom up merge sort removes recursion and builds the sorted array iteratively. It starts by treating each element as a sorted run of size one, then repeatedly merges adjacent runs of increasing size.

This form improves control over memory access and avoids recursion overhead. It is commonly used in systems where stack usage must remain bounded.

Problem

Given an array $A$ of length $n$ , reorder it such that:

A[0] \le A[1] \le \dots \le A[n-1]

Algorithm

Start with run size $1$ . Merge adjacent runs of size $1$ , then size $2$ , then size $4$ , and continue doubling until the whole array is sorted.

bottom_up_merge_sort(A):
    n = length(A)
    size = 1

    while size < n:
        for left in range(0, n, 2 * size):
            mid = min(left + size - 1, n - 1)
            right = min(left + 2 * size - 1, n - 1)

            if mid < right:
                merge(A, left, mid, right)

        size = size * 2

Example

Let:

A = [5, 2, 4, 1]

Pass 1 (size = 1):

[5] + [2] → [2, 5]
[4] + [1] → [1, 4] Array becomes: [2, 5, 1, 4]

Pass 2 (size = 2):

[2, 5] + [1, 4] → [1, 2, 4, 5]

Final sorted array:

[1, 2, 4, 5]

Correctness

Each pass merges sorted runs into larger sorted runs. Since size doubles each iteration, after $\log n$ passes the entire array becomes one sorted run. The merge step maintains order, so correctness follows.

Complexity

Recurrence follows the same structure as merge sort:

T(n) = 2T(n/2) + O(n)

T(n)=2T(n/2)+n

Solution:

T(n) = O(n \log n)

metric	value
time	$O(n \log n)$
space	$O(n)$
passes	$\log n$

Properties

property	value
stable	yes
in-place	no
recursion	none
cache locality	good (sequential access)

Notes

Bottom up merge sort often performs better in practice for large arrays because:

it avoids recursive overhead
it accesses memory sequentially
it fits well with external and disk based sorting

It is also the foundation for many production grade sorting systems.

Implementation

def bottom_up_merge_sort(a):
    n = len(a)
    temp = [0] * n
    size = 1

    def merge(l, mid, r):
        i, j, k = l, mid + 1, l

        while i <= mid and j <= r:
            if a[i] <= a[j]:
                temp[k] = a[i]
                i += 1
            else:
                temp[k] = a[j]
                j += 1
            k += 1

        while i <= mid:
            temp[k] = a[i]
            i += 1
            k += 1

        while j <= r:
            temp[k] = a[j]
            j += 1
            k += 1

        for i in range(l, r + 1):
            a[i] = temp[i]

    while size < n:
        for left in range(0, n, 2 * size):
            mid = min(left + size - 1, n - 1)
            right = min(left + 2 * size - 1, n - 1)
            if mid < right:
                merge(left, mid, right)
        size *= 2

    return a

func BottomUpMergeSort(a []int) {
	n := len(a)
	temp := make([]int, n)

	for size := 1; size < n; size *= 2 {
		for left := 0; left < n; left += 2 * size {
			mid := min(left+size-1, n-1)
			right := min(left+2*size-1, n-1)

			if mid < right {
				merge(a, temp, left, mid, right)
			}
		}
	}
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}