# Batcher Merge Sort

# Batcher Merge Sort

Batcher merge sort is a sorting network algorithm. It sorts two halves recursively, then merges them using Batcher's odd even merge network.

Its comparison pattern is fixed before execution. The same compare and swap operations run regardless of the input values. This makes it useful for parallel machines, SIMD code, GPUs, and hardware circuits.

## Problem

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

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

The cleanest form assumes that $n$ is a power of two.

## Idea

Batcher merge sort follows the same outer structure as merge sort:

1. sort the left half
2. sort the right half
3. merge the sorted halves

The difference is the merge step. Instead of a data dependent linear merge, it uses a fixed odd even merge network.

## Algorithm

```text id="k4s9xp"
batcher_merge_sort(A, lo, n):
    if n <= 1:
        return

    half = n / 2

    batcher_merge_sort(A, lo, half)
    batcher_merge_sort(A, lo + half, half)

    odd_even_merge(A, lo, n, 1)
```

The merge network compares positions at recursively increasing strides.

```text id="p8v2qn"
odd_even_merge(A, lo, n, step):
    double_step = 2 * step

    if double_step < n:
        odd_even_merge(A, lo, n, double_step)
        odd_even_merge(A, lo + step, n, double_step)

        for i from lo + step to lo + n - step - 1 step double_step:
            compare_and_swap(A, i, i + step)
    else:
        compare_and_swap(A, lo, lo + step)
```

## Example

Let:

$$
A = [8, 3, 7, 1, 6, 2, 5, 4]
$$

First sort both halves:

* [8, 3, 7, 1] becomes [1, 3, 7, 8]
* [6, 2, 5, 4] becomes [2, 4, 5, 6]

Then merge them with the odd even merge network.

Final result:

$$
[1,2,3,4,5,6,7,8]
$$

## Correctness

The recursive calls sort both halves. Batcher's odd even merge network correctly merges two sorted sequences by recursively merging their odd and even subsequences, then applying compare and swap operations between neighboring positions. These final comparisons remove the remaining cross inversions. Therefore each merge produces a sorted range. By induction over range size, the whole array is sorted.

## Complexity

| metric             | value                       |
| ------------------ | --------------------------- |
| sequential time    | $O(n \log^2 n)$             |
| parallel depth     | $O(\log^2 n)$               |
| extra space        | $O(\log n)$ recursion stack |
| comparison pattern | fixed                       |

## Properties

| property          | value |
| ----------------- | ----- |
| stable            | no    |
| in-place          | yes   |
| data independent  | yes   |
| comparison based  | yes   |
| parallel friendly | yes   |

## Notes

Batcher merge sort is usually slower than ordinary merge sort on a single CPU because it performs more comparisons. Its value comes from regularity. Since the compare and swap schedule is fixed, different comparisons in the same stage can run in parallel.

It is a core algorithm for sorting networks and remains useful in hardware oriented sorting.

## Implementation

```python id="m4k8xp"
def batcher_merge_sort(a):
    def compare_and_swap(i, j):
        if a[i] > a[j]:
            a[i], a[j] = a[j], a[i]

    def odd_even_merge(lo, n, step):
        double_step = 2 * step

        if double_step < n:
            odd_even_merge(lo, n, double_step)
            odd_even_merge(lo + step, n, double_step)

            for i in range(lo + step, lo + n - step, double_step):
                compare_and_swap(i, i + step)
        else:
            compare_and_swap(lo, lo + step)

    def sort(lo, n):
        if n <= 1:
            return

        half = n // 2
        sort(lo, half)
        sort(lo + half, half)
        odd_even_merge(lo, n, 1)

    sort(0, len(a))
    return a
```

```go id="q8v3tn"
func BatcherMergeSort(a []int) {
	compareAndSwap := func(i, j int) {
		if a[i] > a[j] {
			a[i], a[j] = a[j], a[i]
		}
	}

	var oddEvenMerge func(int, int, int)
	oddEvenMerge = func(lo, n, step int) {
		doubleStep := 2 * step

		if doubleStep < n {
			oddEvenMerge(lo, n, doubleStep)
			oddEvenMerge(lo+step, n, doubleStep)

			for i := lo + step; i < lo+n-step; i += doubleStep {
				compareAndSwap(i, i+step)
			}
		} else {
			compareAndSwap(lo, lo+step)
		}
	}

	var sort func(int, int)
	sort = func(lo, n int) {
		if n <= 1 {
			return
		}

		half := n / 2
		sort(lo, half)
		sort(lo+half, half)
		oddEvenMerge(lo, n, 1)
	}

	sort(0, len(a))
}
```