Algorithm Speed (2.00) :

Array Size (100) :

Bitonic Sort :

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

Bitonic sort is a parallel sorting algorithm that works by creating bitonic sequences (sequences that monotonically increase then decrease) and then merging them into a fully sorted sequence. It is highly efficient for parallel processing architectures like GPUs because its comparison sequence is data-independent.

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

def compAndSwap(a, i, j, dire):
	if (dire == 1 and a[i] > a[j]) or (dire == 0 and a[i] < a[j]):
		a[i], a[j] = a[j], a[i]

def bitonicMerge(a, low, cnt, dire):
	if cnt > 1:
		k = cnt // 2
		for i in range(low, low + k):
			compAndSwap(a, i, i + k, dire)
		bitonicMerge(a, low, k, dire)
		bitonicMerge(a, low + k, k, dire)

def bitonicSort(a, low, cnt, dire):
	if cnt > 1:
		k = cnt // 2
		bitonicSort(a, low, k, 1)
		bitonicSort(a, low + k, k, 0)
		bitonicMerge(a, low, cnt, dire)

def sort(a, N, up):
	bitonicSort(a, 0, N, up)

function compAndSwap(a, i, j, dir) {
	if ((dir === 1 && a[i] > a[j]) || (dir === 0 && a[i] < a[j])) {
		let temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}

function bitonicMerge(a, low, cnt, dir) {
	if (cnt > 1) {
		let k = Math.floor(cnt / 2);
		for (let i = low; i < low + k; i++) {
			compAndSwap(a, i, i + k, dir);
		}
		bitonicMerge(a, low, k, dir);
		bitonicMerge(a, low + k, k, dir);
	}
}

function bitonicSort(a, low, cnt, dir) {
	if (cnt > 1) {
		let k = Math.floor(cnt / 2);
		bitonicSort(a, low, k, 1);
		bitonicSort(a, low + k, k, 0);
		bitonicMerge(a, low, cnt, dir);
	}
}

function sort(a, up) {
	bitonicSort(a, 0, a.length, up);
}

public static void compAndSwap(int[] a, int i, int j, int dir) {
	if ((dir == 1 && a[i] > a[j]) || (dir == 0 && a[i] < a[j])) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}

public static void bitonicMerge(int[] a, int low, int cnt, int dir) {
	if (cnt > 1) {
		int k = cnt / 2;
		for (int i = low; i < low + k; i++) {
			compAndSwap(a, i, i + k, dir);
		}
		bitonicMerge(a, low, k, dir);
		bitonicMerge(a, low + k, k, dir);
	}
}

public static void bitonicSort(int[] a, int low, int cnt, int dir) {
	if (cnt > 1) {
		int k = cnt / 2;
		bitonicSort(a, low, k, 1);
		bitonicSort(a, low + k, k, 0);
		bitonicMerge(a, low, cnt, dir);
	}
}

public static void sort(int[] a, int up) {
	bitonicSort(a, 0, a.length, up);
}

func compAndSwap(a []int, i, j, dir int) {
	if (dir == 1 && a[i] > a[j]) || (dir == 0 && a[i] < a[j]) {
		a[i], a[j] = a[j], a[i]
	}
}

func bitonicMerge(a []int, low, cnt, dir int) {
	if cnt > 1 {
		k := cnt / 2
		for i := low; i < low+k; i++ {
			compAndSwap(a, i, i+k, dir)
		}
		bitonicMerge(a, low, k, dir)
		bitonicMerge(a, low+k, k, dir)
	}
}

func bitonicSort(a []int, low, cnt, dir int) {
	if cnt > 1 {
		k := cnt / 2
		bitonicSort(a, low, k, 1)
		bitonicSort(a, low+k, k, 0)
		bitonicMerge(a, low, cnt, dir)
	}
}

func sort(a []int, up int) {
	bitonicSort(a, 0, len(a), up)
}

void compAndSwap(int a[], int i, int j, int dir) {
	if ((dir == 1 && a[i] > a[j]) || (dir == 0 && a[i] < a[j])) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}

void bitonicMerge(int a[], int low, int cnt, int dir) {
	if (cnt > 1) {
		int k = cnt / 2;
		for (int i = low; i < low + k; i++) {
			compAndSwap(a, i, i + k, dir);
		}
		bitonicMerge(a, low, k, dir);
		bitonicMerge(a, low + k, k, dir);
	}
}

void bitonicSort(int a[], int low, int cnt, int dir) {
	if (cnt > 1) {
		int k = cnt / 2;
		bitonicSort(a, low, k, 1);
		bitonicSort(a, low + k, k, 0);
		bitonicMerge(a, low, cnt, dir);
	}
}

void sort(int a[], int N, int up) {
	bitonicSort(a, 0, N, up);
}