Block Merge Sort

Block merge sort is a stable merge sort variant designed to reduce auxiliary memory while keeping good practical performance. Instead of copying the whole array into a second array, it divides sorted ranges into blocks and rearranges those blocks before finishing with local merges.

The algorithm is more complex than ordinary merge sort, but it gives an important tradeoff: stable sorting with less extra memory.

Problem

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

while preserving the relative order of equal elements and using less than $O(n)$ auxiliary space.

Idea

Standard merge sort merges two sorted ranges by using a temporary array. Block merge sort reduces that storage by working with blocks.

A typical design uses:

The exact implementation varies, but the common principle is to avoid a full size auxiliary array.

Algorithm

block_merge_sort(A):
    sort small runs directly

    size = initial_run_size

    while size < length(A):
        for each adjacent pair of sorted ranges:
            block_merge(A, left, mid, right)

        size = size * 2

The merge procedure is the main part.

block_merge(A, left, mid, right):
    choose block size B

    split A[left..mid] and A[mid+1..right] into blocks

    use a small buffer to move blocks into approximate order

    merge elements locally near block boundaries

    restore the buffer region

Example

Let two sorted ranges be:

Using block size $2$:

The blocks are rearranged approximately by their first elements:

Then local merging inside neighboring block regions produces:

Correctness

Block merge sort keeps the same high level invariant as merge sort: before every merge, the two input ranges are sorted. The block rearrangement step moves groups of elements into an order that narrows where each element can belong. The local merge step then restores exact element order.

Because the final merge compares actual elements and uses stable tie handling, each merged range is sorted and stable. By induction over merge levels, the full array becomes sorted.

Complexity

Some theoretical versions achieve stable in-place merging with $O(1)$ extra words, but the implementations are intricate and have larger constants.

Properties

Notes

Block merge sort is useful when stability matters and memory must be lower than a full auxiliary array. In ordinary application code, standard merge sort or Timsort is often preferred because they are simpler and faster on typical data.

Block merge sort mainly matters as a systems and library sorting technique.

Implementation

This simplified implementation demonstrates block style merging with a fixed buffer. It keeps the main idea visible, but it is not a fully optimized production block merge sort.

def block_merge_sort(a):
    n = len(a)
    if n <= 1:
        return a

    temp = []

    def merge_with_buffer(l, mid, r):
        temp.clear()

        i = l
        j = mid + 1

        while i <= mid and j <= r:
            if a[i] <= a[j]:
                temp.append(a[i])
                i += 1
            else:
                temp.append(a[j])
                j += 1

        while i <= mid:
            temp.append(a[i])
            i += 1

        while j <= r:
            temp.append(a[j])
            j += 1

        for k, value in enumerate(temp):
            a[l + k] = value

    size = 1
    while size < n:
        for l in range(0, n, 2 * size):
            mid = min(l + size - 1, n - 1)
            r = min(l + 2 * size - 1, n - 1)
            if mid < r:
                merge_with_buffer(l, mid, r)
        size *= 2

    return a

func BlockMergeSort(a []int) {
	n := len(a)
	if n <= 1 {
		return
	}

	temp := make([]int, 0, n)

	mergeWithBuffer := func(l, mid, r int) {
		temp = temp[:0]

		i, j := l, mid+1

		for i <= mid && j <= r {
			if a[i] <= a[j] {
				temp = append(temp, a[i])
				i++
			} else {
				temp = append(temp, a[j])
				j++
			}
		}

		for i <= mid {
			temp = append(temp, a[i])
			i++
		}

		for j <= r {
			temp = append(temp, a[j])
			j++
		}

		for k, v := range temp {
			a[l+k] = v
		}
	}

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

			if mid < r {
				mergeWithBuffer(l, mid, r)
			}
		}
	}
}