Bitonic Merge Network

The bitonic merge network is the core component of bitonic sorting. It takes a bitonic sequence and transforms it into a fully sorted sequence using a fixed pattern of compare and exchange operations.

A sequence is bitonic when it consists of an increasing part followed by a decreasing part, or can be rotated into that form.

Problem

Given a bitonic sequence of length $n$, produce a sorted sequence in nondecreasing order.

Assume $n$ is a power of two for the standard construction.

Algorithm

The merge proceeds in stages. Each stage compares elements separated by a fixed distance, then recursively merges the resulting halves.

bitonic_merge_network(A, lo, n, ascending):
    if n <= 1:
        return

    k = n / 2

    for i from lo to lo + k - 1:
        compare_exchange(A, i, i + k, ascending)

    bitonic_merge_network(A, lo, k, ascending)
    bitonic_merge_network(A, lo + k, k, ascending)

At the first stage, each element in the first half is compared with a corresponding element in the second half.

Comparator

compare_exchange(A, i, j, ascending):
    if ascending:
        if A[i] > A[j]:
            swap A[i], A[j]
    else:
        if A[i] < A[j]:
            swap A[i], A[j]

All comparisons in a stage are independent and can be executed in parallel.

Key Property

After the first compare and exchange stage:

• The smaller elements of each pair move to the first half
• The larger elements move to the second half

Both halves remain bitonic.

This property enables recursive merging.

Example

Given a bitonic sequence:

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

First stage comparisons:

(1, 8), (4, 6), (7, 3), (9, 2)

After compare and exchange:

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

Now both halves are bitonic:

• First half: $[1, 4, 3, 2]$
• Second half: $[8, 6, 7, 9]$

Recursively applying the same process yields a sorted array.

Complexity

measure	value
comparators	$O(n \log n)$
depth	$O(\log n)$
extra space	$O(1)$
input dependence	none

This is more efficient than the full bitonic sort, which uses $O(n \log^2 n)$ comparators.

Correctness

The correctness relies on the bitonic property. In a bitonic sequence, for every pair $(A[i], A[i + k])$, the smaller value belongs in the first half and the larger value belongs in the second half.

After the first stage, each half becomes a smaller bitonic sequence. By induction, recursively merging both halves produces sorted subsequences. Combining these subsequences yields a fully sorted sequence.

Practical Considerations

• Works best for power of two sizes.
• Used as a building block in bitonic sort and GPU sorting.
• Regular structure makes it suitable for SIMD and hardware implementation.
• Requires the input to be bitonic.
• Padding can handle non power of two inputs.

When to Use

Use the bitonic merge network when:

• merging bitonic sequences
• building a bitonic sorting network
• implementing GPU or SIMD sorting
• fixed comparator patterns are required

Avoid using it alone on arbitrary unsorted input. It assumes the input is already bitonic.

Implementation

func BitonicMergeNetwork(a []int, lo, n int, ascending bool) {
	if n <= 1 {
		return
	}

	k := n / 2

	for i := lo; i < lo+k; i++ {
		if ascending {
			if a[i] > a[i+k] {
				a[i], a[i+k] = a[i+k], a[i]
			}
		} else {
			if a[i] < a[i+k] {
				a[i], a[i+k] = a[i+k], a[i]
			}
		}
	}

	BitonicMergeNetwork(a, lo, k, ascending)
	BitonicMergeNetwork(a, lo+k, k, ascending)
}

def bitonic_merge_network(a, lo, n, ascending=True):
    if n <= 1:
        return

    k = n // 2

    for i in range(lo, lo + k):
        if ascending:
            if a[i] > a[i + k]:
                a[i], a[i + k] = a[i + k], a[i]
        else:
            if a[i] < a[i + k]:
                a[i], a[i + k] = a[i + k], a[i]

    bitonic_merge_network(a, lo, k, ascending)
    bitonic_merge_network(a, lo + k, k, ascending)