Bitonic Sort Program with Explanation and Code

2025-11-19 bitonic sort parallel sorting GPU sorting sorting networks bitonic sequence divide and merge sorting algorithm programs python bitonic sort c bitonic sort javascript bitonic sort csharp bitonic sort php bitonic sort

Bitonic Sort is a parallel sorting algorithm based on bitonic sequences and is widely used in GPU and multi-processor systems. This page explains the algorithm step-by-step and provides complete examples in Python, C, JavaScript, PHP, and C#. Ideal for learning advanced sorting concepts.

Program Explanation

What is Bitonic Sort?

Bitonic Sort is a parallel sorting algorithm that works by constructing a special sequence called a bitonic sequence — a sequence that first increases and then decreases (or vice versa). Once a bitonic sequence is formed, the algorithm recursively splits and merges the sequence until it becomes fully sorted. Bitonic Sort is efficient on parallel architectures like GPUs and multiprocessor systems.

Steps to Solve

  1. Create a bitonic sequence by arranging elements in alternating ascending/descending order.
  2. Split the sequence into two halves.
  3. Compare and swap elements to form two smaller bitonic sequences.
  4. Recursively apply the merging process to sort each half.
  5. Continue splitting until subsequences of size 1 are formed.
  6. Combine all sorted subsequences to form the final sorted array.
  7. The array becomes fully sorted in ascending order.

Key Points

  • Mainly used in parallel computing due to predictable data patterns.
  • Time complexity: O(n log² n).
  • Works best when array size is a power of 2.
  • Not efficient on single-threaded CPUs compared to Quick Sort or Merge Sort.
  • Used in high-performance computing systems and hardware-level sorting.

Program Code


def compare(arr, i, j, direction):
    if direction == 1 and arr[i] > arr[j]:
        arr[i], arr[j] = arr[j], arr[i]
    if direction == 0 and arr[i] < arr[j]:
        arr[i], arr[j] = arr[j], arr[i]

def bitonic_merge(arr, low, cnt, direction):
    if cnt > 1:
        k = cnt // 2
        for i in range(low, low + k):
            compare(arr, i, i + k, direction)
        bitonic_merge(arr, low, k, direction)
        bitonic_merge(arr, low + k, k, direction)

def bitonic_sort(arr, low, cnt, direction):
    if cnt > 1:
        k = cnt // 2
        bitonic_sort(arr, low, k, 1)
        bitonic_sort(arr, low + k, k, 0)
        bitonic_merge(arr, low, cnt, direction)

arr = list(map(int, input("Enter numbers: ").split()))
n = len(arr)

bitonic_sort(arr, 0, n, 1)
print("Sorted array:", arr)
      

#include <stdio.h>

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

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

        bitonicMerge(arr, low, k, dir);
        bitonicMerge(arr, low + k, k, dir);
    }
}

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

int main() {
    int n;
    printf("Enter number of elements: ");
    scanf("%d", &n);

    int arr[n];
    printf("Enter elements: ");
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    bitonicSort(arr, 0, n, 1);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}
      

function compare(arr, i, j, dir) {
  if ((dir === 1 && arr[i] > arr[j]) || (dir === 0 && arr[i] < arr[j])) {
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
}

function bitonicMerge(arr, low, cnt, dir) {
  if (cnt > 1) {
    let k = Math.floor(cnt / 2);

    for (let i = low; i < low + k; i++)
      compare(arr, i, i + k, dir);

    bitonicMerge(arr, low, k, dir);
    bitonicMerge(arr, low + k, k, dir);
  }
}

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

let arr = prompt("Enter numbers:").split(" ").map(Number);
bitonicSort(arr, 0, arr.length, 1);
console.log("Sorted array:", arr);
      

using System;

class Program {

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

    static void BitonicMerge(int[] arr, int low, int cnt, int dir) {
        if (cnt > 1) {
            int k = cnt / 2;

            for (int i = low; i < low + k; i++)
                Compare(arr, i, i + k, dir);

            BitonicMerge(arr, low, k, dir);
            BitonicMerge(arr, low + k, k, dir);
        }
    }

    static void BitonicSort(int[] arr, int low, int cnt, int dir) {
        if (cnt > 1) {
            int k = cnt / 2;
            BitonicSort(arr, low, k, 1);
            BitonicSort(arr, low + k, k, 0);
            BitonicMerge(arr, low, cnt, dir);
        }
    }

    static void Main() {
        Console.Write("Enter numbers: ");
        int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

        BitonicSort(arr, 0, arr.Length, 1);

        Console.Write("Sorted array: ");
        foreach (int x in arr)
            Console.Write(x + " ");
    }
}
      

<?php

function compareVals(&$arr, $i, $j, $dir) {
    if (($dir == 1 && $arr[$i] > $arr[$j]) || ($dir == 0 && $arr[$i] < $arr[$j])) {
        $temp = $arr[$i];
        $arr[$i] = $arr[$j];
        $arr[$j] = $temp;
    }
}

function bitonicMerge(&$arr, $low, $cnt, $dir) {
    if ($cnt > 1) {
        $k = intdiv($cnt, 2);

        for ($i = $low; $i < $low + $k; $i++)
            compareVals($arr, $i, $i + $k, $dir);

        bitonicMerge($arr, $low, $k, $dir);
        bitonicMerge($arr, $low + $k, $k, $dir);
    }
}

function bitonicSort(&$arr, $low, $cnt, $dir) {
    if ($cnt > 1) {
        $k = intdiv($cnt, 2);
        bitonicSort($arr, $low, $k, 1);
        bitonicSort($arr, $low + $k, $k, 0);
        bitonicMerge($arr, $low, $cnt, $dir);
    }
}

$arr = array_map('intval', explode(" ", readline("Enter numbers: ")));
bitonicSort($arr, 0, count($arr), 1);

echo "Sorted array: " . implode(" ", $arr);

?>
1