# Bitonic Sorting Network

# Bitonic Sorting Network

A bitonic sorting network is a fixed sequence of compare and exchange operations that sorts a fixed number of elements. It is based on the idea of repeatedly building bitonic sequences and merging them.

A bitonic sequence increases and then decreases, or can be rotated into that shape. The network first creates bitonic sequences of small size, then merges them into larger sorted sequences until the full input is sorted.

## Problem

Given $n$ input values, where $n$ is usually a power of two, sort them in nondecreasing order using a fixed comparator network.

Unlike quicksort or merge sort, the comparison schedule does not depend on the input values.

## Algorithm

The iterative network form uses nested stages.

```text id="cmo3tc"
bitonic_sorting_network(A):
    n = length(A)

    for size = 2; size <= n; size *= 2:
        for stride = size / 2; stride > 0; stride /= 2:
            for i from 0 to n - 1:
                j = i xor stride

                if j > i:
                    ascending = (i & size) == 0

                    if ascending and A[i] > A[j]:
                        swap A[i], A[j]

                    if not ascending and A[i] < A[j]:
                        swap A[i], A[j]
```

The partner index is:

$$
j = i \oplus stride
$$

The value of `stride` decides which wires are compared in the current stage.

## Comparator

Each comparator sorts a pair of positions.

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

In a hardware or SIMD implementation, all independent comparators in the same stage can run at the same time.

## Example

For $n = 4$, the network performs these stages:

```text id="sfzhnb"
compare (0, 1) ascending
compare (2, 3) descending

compare (0, 2) ascending
compare (1, 3) ascending

compare (0, 1) ascending
compare (2, 3) ascending
```

Starting with:

$$
[4, 1, 3, 2]
$$

The final output is:

$$
[1, 2, 3, 4]
$$

## Complexity

| measure          | value           |
| ---------------- | --------------- |
| comparators      | $O(n \log^2 n)$ |
| network depth    | $O(\log^2 n)$   |
| extra space      | $O(1)$          |
| input dependence | none            |

The same comparator pattern runs for sorted, reversed, random, and duplicate heavy inputs.

## Correctness

The network builds sorted sequences by repeatedly applying bitonic merge. A bitonic merge takes a bitonic sequence and turns it into a sorted sequence by first comparing elements separated by half the sequence length, then recursively merging both halves.

The construction ensures that each larger stage receives valid bitonic input. By induction over sequence size, every stage produces correctly sorted subsequences. At the final stage, the full sequence is sorted.

## Practical Considerations

* It maps well to hardware, SIMD, and GPUs.
* It has predictable control flow.
* It performs more comparisons than many adaptive or comparison based sorts.
* It works best for power of two lengths.
* Non power of two inputs can be padded with sentinel values.
* It is often used as a local sorting primitive rather than a full CPU array sort.

## When to Use

Use a bitonic sorting network when:

* input size is fixed
* predictable execution matters
* parallel compare and exchange is cheap
* SIMD, GPU, FPGA, or hardware sorting is targeted
* branches and input dependent control flow should be avoided

For general CPU sorting of large arrays, introsort, merge sort, radix sort, or sample sort usually performs less work.

## Implementation

```go id="v7wle6"
func BitonicSortingNetwork(a []int) {
	n := len(a)

	for size := 2; size <= n; size <<= 1 {
		for stride := size >> 1; stride > 0; stride >>= 1 {
			for i := 0; i < n; i++ {
				j := i ^ stride

				if j > i {
					ascending := (i & size) == 0

					if ascending && a[i] > a[j] {
						a[i], a[j] = a[j], a[i]
					}

					if !ascending && a[i] < a[j] {
						a[i], a[j] = a[j], a[i]
					}
				}
			}
		}
	}
}
```

```python id="4t7w41"
def bitonic_sorting_network(a):
    n = len(a)

    size = 2
    while size <= n:
        stride = size // 2

        while stride > 0:
            for i in range(n):
                j = i ^ stride

                if j > i:
                    ascending = (i & size) == 0

                    if ascending and a[i] > a[j]:
                        a[i], a[j] = a[j], a[i]

                    if not ascending and a[i] < a[j]:
                        a[i], a[j] = a[j], a[i]

            stride //= 2

        size *= 2
```