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:

sort the left half
sort the right half
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

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.

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

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

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))
}