Bitonic sort is a comparison-based sorting algorithm that can be run in
parallel.
It focuses on converting a random sequence of numbers into a
*bitonic sequence*, one that monotonically increases, then
decreases.
Rotations of a bitonic sequence are also bitonic.

More specifically, bitonic sort can be modelled as a type of *sorting
network*.
The initial unsorted sequence enters through input pipes,
where a series of comparators switch two entries to be in either
increasing or decreasing order.

The algorithm, created by Ken Batcher in 1968, consists of two parts. First, the unsorted sequence is built into a bitonic sequence; then, the series is split multiple times into smaller sequences until the input is in sorted order.

The bitonic split is a procedure that cuts one bitonic sequence into
two smaller ones,
where all the elements of the first sequence are less
than or equal to the ones in the second. Looking at the example below,
a bitonic sequence is divided between its two halves, and the *n
^{th}* element in each part is compared with each other.
If
they are out of order, they are swapped. Applying this procedure
repeatedly onto the smaller lists,
the result is a sorted sequence in
ascending order.

Before the sorting can occur, the original sequence must first be transformed into a bitonic one. Note that two numbers by themselves are a bitonic sequence; from that, the sequence can be partitioned into smaller bitonic ones and then merged together.

The building algorithm is a variation of the bitonic split: two adjacent bitonic sequences are split and sorted in ascending order, the next two in descending order, and so on. The orinial two sequences are now a single bitonic sequence. This procedure continues until the entirety of the input has been converted.

Here is an example of the build algorithm applied to a list of integers:

This code, written in C, applies bitonic sort to a list of integers given in a text file.

#include "stdio.h"
void merge_up(int *arr, int n) {
int step=n/2,i,j,k,temp;
while (step > 0) {
for (i=0; i < n; i+=step*2) {
for (j=i,k=0;k < step;j++,k++) {
if (arr[j] > arr[j+step]) {
// swap
temp = arr[j];
arr[j]=arr[j+step];
arr[j+step]=temp;
}
}
}
step /= 2;
}
}
void merge_down(int *arr, int n) {
int step=n/2,i,j,k,temp;
while (step > 0) {
for (i=0; i < n; i+=step*2) {
for (j=i,k=0;k < step;j++,k++) {
if (arr[j] < arr[j+step]) {
// swap
temp = arr[j];
arr[j]=arr[j+step];
arr[j+step]=temp;
}
}
}
step /= 2;
}
}
void printArray(int *arr, int n) {
int i;
printf("[%d",arr[0]);
for (i=1; i < n;i++) {
printf(",%d",arr[i]);
}
printf("]\n");
}
int main(int argc, char **argv) {
int n, *arr, i,s;
FILE *fp = fopen(argv[1],"r");
if (fp == NULL) {
fprintf(stderr,"file not found\n");
exit(1);
}
// first line gives number of numbers to be sorted
fscanf(fp,"%d",&n);
// allocate space and read all the numbers
arr = (int *)malloc(n*sizeof(int));
for (i=0; i < n; i++) {
fscanf(fp,"%d",(arr+i));
}
// print array before
printArray(arr,n);
// do merges
for (s=2; s <= n; s*=2) {
for (i=0; i < n;) {
merge_up((arr+i),s);
merge_down((arr+i+s),s);
i += s*2;
}
}
printArray(arr,n);
}

When run in serial, the bitonic sorting network completes its work in
*O(n log ^{2}n)* comparisons, which falls short of the
ideal comparison-based sort efficiency of

- John Mellor-Crummy.
*Bitonic Sort*. Rice University: - Thomas Anastasio.
*Bitonic Sorting*. facultyfp.salisbury.edu .