# Bottom Up Merge Sort

# 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.

```text id="z3k1xw"
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

```python id="y2m8qp"
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
```

```go id="h8s2ka"
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
}
```