# Parallel Bitonic Sort

# Parallel Bitonic Sort

Parallel bitonic sort is a sorting network based algorithm. It sorts by repeatedly forming bitonic sequences and then merging them into sorted order.

A bitonic sequence first increases and then decreases, or can be rotated into that shape. The algorithm works especially well on parallel hardware because the compare and exchange pattern is regular and independent of the input values.

## Problem

Given an array $A$ of size $n$, sort the elements in nondecreasing order using parallel compare and exchange steps.

For the cleanest version, assume $n$ is a power of two.

## Bitonic Sequence

A sequence is bitonic when it consists of two monotone parts, one increasing and one decreasing.

Examples:

```text id="5wnkiq"
[1, 4, 8, 9, 7, 3, 2]
[9, 7, 3, 1, 2, 4, 8]
```

Bitonic sort creates such sequences recursively, then applies a bitonic merge.

## Algorithm

The recursive form sorts one half ascending and the other half descending. This creates a bitonic sequence. Then it merges the whole range in the desired direction.

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

    k = n / 2

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

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

The merge step compares elements separated by half the range length.

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

    k = n / 2

    parallel for i from lo to lo + k - 1:
        compare_exchange(A[i], A[i + k], dir)

    parallel:
        bitonic_merge(A, lo, k, dir)
        bitonic_merge(A, lo + k, k, dir)
```

## Compare and Exchange

```text id="8ed2pm"
compare_exchange(x, y, ascending):
    if ascending and x > y:
        swap x, y

    if descending and x < y:
        swap x, y
```

This primitive is independent for many pairs, which makes the algorithm suitable for SIMD, GPU, and sorting network implementations.

## Complexity

| measure        | value                             |
| -------------- | --------------------------------- |
| comparisons    | $O(n \log^2 n)$                   |
| parallel depth | $O(\log^2 n)$                     |
| extra space    | $O(1)$ for in place array version |
| best case      | same as worst case                |

Unlike quicksort or mergesort, bitonic sort performs the same compare and exchange schedule regardless of input order.

## Correctness

The recursive sort step produces two sorted halves in opposite directions, so their concatenation is bitonic. Bitonic merge has the property that after comparing pairs separated by half the length, each half remains bitonic and all elements in the first half belong before all elements in the second half for the chosen direction. Recursively merging both halves therefore produces a sorted sequence.

## Practical Considerations

* Works best when $n$ is a power of two.
* Padding can handle other sizes.
* Performs more comparisons than comparison sorts such as quicksort or merge sort.
* Regular memory access makes it attractive on GPUs and SIMD units.
* Runtime is data independent, which can help when predictable control flow matters.

## When to Use

Use parallel bitonic sort when:

* the hardware favors regular compare and exchange patterns
* data size is moderate
* SIMD or GPU execution is available
* predictable branch free execution matters
* a sorting network is desired

For large CPU based sorting, parallel quicksort, parallel merge sort, or parallel sample sort usually performs less work.

## Implementation (Go, simplified)

```go id="kcyzck"
func ParallelBitonicSort(a []int) {
	if len(a) <= 1 {
		return
	}
	bitonicSort(a, 0, len(a), true)
}

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

	k := n / 2

	done := make(chan struct{}, 2)

	go func() {
		bitonicSort(a, lo, k, true)
		done <- struct{}{}
	}()

	go func() {
		bitonicSort(a, lo+k, k, false)
		done <- struct{}{}
	}()

	<-done
	<-done

	bitonicMerge(a, lo, n, ascending)
}

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

	k := n / 2

	for i := lo; i < lo+k; i++ {
		compareExchange(a, i, i+k, ascending)
	}

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

func compareExchange(a []int, i, j int, ascending bool) {
	if ascending {
		if a[i] > a[j] {
			a[i], a[j] = a[j], a[i]
		}
		return
	}

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