# Bitonic Merge Network

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

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

```text id="4t3m8k"
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:

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

```go id="9v4c8x"
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)
}
```

```python id="3x9m1k"
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)
```