# Bitonic Sort

# Bitonic Sort

Bitonic sort is a comparison sorting algorithm based on bitonic sequences. It is important because its compare and swap pattern is fixed, which makes it suitable for parallel hardware and sorting networks.

A bitonic sequence first increases and then decreases, or can be rotated into that form.

## Problem

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

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

Bitonic sort is simplest when $n$ is a power of two.

## Idea

The algorithm has two main operations:

| operation     | purpose                                             |
| ------------- | --------------------------------------------------- |
| bitonic build | recursively create a bitonic sequence               |
| bitonic merge | transform a bitonic sequence into a sorted sequence |

To sort ascending:

1. sort the first half ascending
2. sort the second half descending
3. merge the resulting bitonic sequence ascending

## Algorithm

```text id="s9k2qp"
bitonic_sort(A, lo, n, direction):
    if n <= 1:
        return

    k = n / 2

    bitonic_sort(A, lo, k, ascending)
    bitonic_sort(A, lo + k, k, descending)

    bitonic_merge(A, lo, n, direction)
```

```text id="m4x8vt"
bitonic_merge(A, lo, n, direction):
    if n <= 1:
        return

    k = n / 2

    for i from lo to lo + k - 1:
        compare_and_swap(A, i, i + k, direction)

    bitonic_merge(A, lo, k, direction)
    bitonic_merge(A, lo + k, k, direction)
```

## Example

Let:

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

Build a bitonic sequence by sorting halves in opposite directions:

* left ascending
* right descending

Then repeatedly compare elements separated by half the range and recurse.

Final result:

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

## Correctness

The algorithm first constructs a bitonic sequence. The bitonic merge step compares corresponding elements across the two halves and moves smaller values into the ascending half and larger values into the descending half. Each half remains bitonic, so recursive merging eventually produces sorted singleton ranges. Therefore the whole sequence becomes sorted.

## Complexity

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

The fixed comparison structure makes the algorithm useful even though its sequential time is worse than merge sort or quicksort.

## Properties

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

## Notes

Bitonic sort is rarely chosen for ordinary CPU sorting because $O(n \log^2 n)$ is slower than $O(n \log n)$ algorithms. Its strength is regular structure. It is useful on GPUs, SIMD hardware, and parallel sorting networks where predictable compare and swap schedules matter.

## Implementation

```python id="k8s2xp"
def bitonic_sort(a):
    def compare_and_swap(i, j, ascending):
        if (ascending and a[i] > a[j]) or ((not ascending) and a[i] < a[j]):
            a[i], a[j] = a[j], a[i]

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

        k = n // 2
        for i in range(lo, lo + k):
            compare_and_swap(i, i + k, ascending)

        merge(lo, k, ascending)
        merge(lo + k, k, ascending)

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

        k = n // 2
        sort(lo, k, True)
        sort(lo + k, k, False)
        merge(lo, n, ascending)

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

```go id="t2q9vm"
func BitonicSort(a []int) {
	var compareAndSwap func(int, int, bool)
	compareAndSwap = func(i, j int, ascending bool) {
		if (ascending && a[i] > a[j]) || (!ascending && a[i] < a[j]) {
			a[i], a[j] = a[j], a[i]
		}
	}

	var merge func(int, int, bool)
	merge = func(lo, n int, ascending bool) {
		if n <= 1 {
			return
		}

		k := n / 2
		for i := lo; i < lo+k; i++ {
			compareAndSwap(i, i+k, ascending)
		}

		merge(lo, k, ascending)
		merge(lo+k, k, ascending)
	}

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

		k := n / 2
		sort(lo, k, true)
		sort(lo+k, k, false)
		merge(lo, n, ascending)
	}

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