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:

sort the first half ascending
sort the second half descending
merge the resulting bitonic sequence ascending

Algorithm

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)

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

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

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)
}