Bitonic Sort: Overview

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.

Bitonic Build

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.

Sequential Code

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

Exported from Notepad++

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

Efficiency

When run in serial, the bitonic sorting network completes its work in O(n log²n) comparisons, which falls short of the ideal comparison-based sort efficiency of O(n log n). Parallel versions of the sort, however, can lead to dramatic speedups, depending on the implementation.