Algorithm Speed (2.00) :

Array Size (100) :

Bitonic Sort :

Author(s) : Kenneth E. Batcher Date : 1960s

Bitonic sort is a sorting algorithm designed for parallel computing environments. It operates on a bitonic sequence (a sequence that is first increasing and then decreasing, or vice versa). The algorithm recursively divides the sequence into smaller bitonic sub-sequences and sorts them using a specific compare-swap operation. Bitonic sort leverages the capabilities of parallel processors to achieve efficient sorting. However, its practical use often requires specialized hardware or algorithms tailored for parallel execution.

Time Complexity	O(log² n)
Best Case	O(log² n)
Worst Case	O(n log² n)
Space Complexity	O(1)
Stable	No

def bitonic_merge(arr, lo, cnt, dir):
	if cnt > 1:
		mid = lo + cnt // 2
		if dir == 1:
			bitonic_merge(arr, lo, cnt // 2, 1)
			bitonic_merge(arr, mid, cnt // 2, 0)
		else:
			bitonic_merge(arr, mid, cnt // 2, 0)
			bitonic_merge(arr, lo, cnt // 2, 1)
	if dir == 0:
		if arr[lo] > arr[lo + cnt - 1]:
			arr[lo], arr[lo + cnt - 1] = arr[lo + cnt - 1], arr[lo]

def bitonic_sort(arr, n, dir):
	if n > 1:
		for i in range(0, n, 2):
			bitonic_merge(arr, i, 2, dir)
		bitonic_sort(arr, n // 2, 0 if dir else 1)
		bitonic_sort(arr, n // 2, 1 if dir else 0)

# Test array
arr = [8, 1, 2, 3, 7, 6, 5, 4]
bitonic_sort(arr, len(arr), 1)
print('Sorted array:', arr)

function bitonicMerge(arr, lo, cnt, dir) {
	if (cnt > 1) {
		const mid = lo + Math.floor(cnt / 2);
		if (dir === 1) {
			bitonicMerge(arr, lo, cnt / 2, 1);
			bitonicMerge(arr, mid, cnt / 2, 0);
		} else {
			bitonicMerge(arr, mid, cnt / 2, 0);
			bitonicMerge(arr, lo, cnt / 2, 1);
		}
	}
	if (dir === 0) {
		if (arr[lo] > arr[lo + cnt - 1]) {
			[arr[lo], arr[lo + cnt - 1]] = [arr[lo + cnt - 1], arr[lo]];
		}
	}
}

function bitonicSort(arr, n, dir) {
	if (n > 1) {
		for (let i = 0; i < n; i += 2) {
			bitonicMerge(arr, i, 2, dir);
		}
		bitonicSort(arr, Math.floor(n / 2), 0 === dir ? 0 : 1);
		bitonicSort(arr, Math.floor(n / 2), 1 === dir ? 0 : 1);
	}
}

// Test array
const arr = [8, 1, 2, 3, 7, 6, 5, 4];
bitonicSort(arr, arr.length, 1);
console.log('Sorted array:', arr);

public class BitonicSort {
	public static void bitonicMerge(int[] arr, int lo, int cnt, int dir) {
		if (cnt > 1) {
			int mid = lo + cnt / 2;
			if (dir == 1) {
				bitonicMerge(arr, lo, cnt / 2, 1);
				bitonicMerge(arr, mid, cnt / 2, 0);
			} else {
				bitonicMerge(arr, mid, cnt / 2, 0);
				bitonicMerge(arr, lo, cnt / 2, 1);
			}
		}
		if (dir == 0 && arr[lo] > arr[lo + cnt - 1]) {
			swap(arr, lo, lo + cnt - 1);
		}
	}

	private static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

	public static void bitonicSort(int[] arr, int n, int dir) {
		if (n > 1) {
			for (int i = 0; i < n; i += 2) {
				bitonicMerge(arr, i, 2, dir);
			}
			bitonicSort(arr, n / 2, 0 if dir == 1 else 1);
			bitonicSort(arr, n / 2, 1 if dir == 1 else 0);
		}
	}

	public static void main(String[] args) {
		int[] arr = {8, 1, 2, 3, 7, 6, 5, 4};
		bitonicSort(arr, arr.length, 1);
		System.out.print("Sorted array is: ");
		for (int num : arr) {
			System.out.print(num + " ");
		}
	}
}

package main

func bitonicMerge(arr []int, lo, cnt, dir int) {
	if cnt > 1 {
		mid := lo + cnt/2
		if dir == 1 {
			bitonicMerge(arr, lo, cnt/2, 1)
			bitonicMerge(arr, mid, cnt/2, 0)
		} else {
			bitonicMerge(arr, mid, cnt/2, 0)
			bitonicMerge(arr, lo, cnt/2, 1)
		}
	}
	if dir == 0 && arr[lo] > arr[lo+cnt-1] {
		arr[lo], arr[lo+cnt-1] = arr[lo+cnt-1], arr[lo]
	}
}

func bitonicSort(arr []int, n, dir int) {
	if n > 1 {
		for i := 0; i < n; i += 2 {
			bitonicMerge(arr, i, 2, dir)
		}
		bitonicSort(arr[:n/2], n/2, 0 if dir == 1 else 1)
		bitonicSort(arr[n/2:], n/2, 1 if dir == 1 else 0)
	}
}

func main() {
	arr := []int{8, 1, 2, 3, 7, 6, 5, 4}
	bitonicSort(arr, len(arr), 1)
	println("Sorted array is:", arr)
}

#include <stdio.h>

void swap(int *a, int *b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}

void bitonicMerge(int arr[], int lo, int cnt, int dir) {
	if (cnt > 1) {
		int mid = lo + cnt / 2;
		if (dir == 1) {
			bitonicMerge(arr, lo, cnt / 2, 1);
			bitonicMerge(arr, mid, cnt / 2, 0);
		} else {
			bitonicMerge(arr, mid, cnt / 2, 0);
			bitonicMerge(arr, lo, cnt / 2, 1);
		}
	}
	if (dir == 0 && arr[lo] > arr[lo + cnt - 1]) {
		swap(&arr[lo], &arr[lo + cnt - 1]);
	}
}

void bitonicSort(int arr[], int n, int dir) {
	if (n > 1) {
		for (int i = 0; i < n; i += 2) {
			bitonicMerge(arr, i, 2, dir);
		}
		bitonicSort(arr, n / 2, 0 if dir == 1 else 1);
		bitonicSort(arr + n / 2, n / 2, 1 if dir == 1 else 0);
	}
}

int main() {
	int arr[] = {8, 1, 2, 3, 7, 6, 5, 4};
	int n = sizeof(arr) / sizeof(arr[0]);
	bitonicSort(arr, n, 1);
	printf("Sorted array is: ");
	for (int i = 0; i < n; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
	return 0;
}