Example: Bitonic Sort Implementation in C

// Bitonic Sort Implementation
#include <stdio.h>
#include <stdlib.h> // For malloc and free, though not strictly needed for this fixed-size example

// Function to swap two elements
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Function to compare and swap elements based on direction
// dir = 1 for ascending, 0 for descending
void compareAndSwap(int arr[], int i, int j, int dir) {
    if ((arr[i] > arr[j] && dir == 1) || (arr[i] < arr[j] && dir == 0)) {
        swap(&arr[i], &arr[j]);
    }
}

// Function to merge a bitonic sequence
// It splits the sequence into two halves and recursively merges them
// 'dir' indicates the overall sorting direction (1 for ascending, 0 for descending)
void bitonicMerge(int arr[], int low, int count, int dir) {
    if (count > 1) {
        int k = count / 2;
        // Compare elements in the first half with elements in the second half
        for (int i = low; i < low + k; i++) {
            compareAndSwap(arr, i, i + k, dir);
        }
        // Recursively merge the two halves
        bitonicMerge(arr, low, k, dir);
        bitonicMerge(arr, low + k, k, dir);
    }
}

// Function to implement bitonic sort
// It recursively sorts two halves of the array in opposite directions
// and then merges them using bitonicMerge
// 'dir' indicates the desired sorting direction for this sub-sequence
void bitonicSort(int arr[], int low, int count, int dir) {
    if (count > 1) {
        int k = count / 2;
        // Sort first half in ascending order
        bitonicSort(arr, low, k, 1);
        // Sort second half in descending order
        bitonicSort(arr, low + k, k, 0);
        // Merge the entire bitonic sequence in the desired 'dir'
        bitonicMerge(arr, low, count, dir);
    }
}

// Helper function to print the array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    // Step 1: Define an array to be sorted.
    // The size of the array must be a power of 2 for this implementation.
    int arr[] = {3, 7, 4, 8, 6, 2, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, n);

    // Step 2: Call the bitonicSort function to sort the array in ascending order (dir = 1).
    bitonicSort(arr, 0, n, 1);

    printf("Sorted array:   ");
    printArray(arr, n);

    return 0;
}