Example: Bitonic Sort Implementation in C++

// Bitonic Sort Implementation
#include <iostream>
#include <vector>
#include <algorithm> // For std::swap

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

// Function to merge a bitonic sequence in a specified direction
// low: starting index of the sub-array
// cnt: number of elements in the sub-array
// dir: 1 for ascending merge, 0 for descending merge
void bitonicMerge(std::vector<int>& arr, int low, int cnt, int dir) {
    if (cnt > 1) {
        int k = cnt / 2; // Half the current segment size
        // Compare elements k distance apart within the segment
        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
// low: starting index of the sub-array
// cnt: number of elements in the sub-array
// dir: 1 for ascending sort, 0 for descending sort
void bitonicSort(std::vector<int>& arr, int low, int cnt, int dir) {
    if (cnt > 1) {
        int k = cnt / 2;
        // Step 1: Recursively sort the first half in ascending order
        bitonicSort(arr, low, k, 1);
        // Step 2: Recursively sort the second half in descending order
        bitonicSort(arr, low + k, k, 0);
        // Step 3: Merge the entire sequence in the specified direction
        bitonicMerge(arr, low, cnt, dir);
    }
}

// Helper function to call bitonicSort for the entire array
// N: total number of elements in the array
// dir: 1 for ascending sort, 0 for descending sort
void sort(std::vector<int>& arr, int N, int dir) {
    bitonicSort(arr, 0, N, dir);
}

int main() {
    std::vector<int> arr = {3, 7, 4, 8, 6, 2, 1, 5};
    int N = arr.size();

    std::cout << "Original array: ";
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // Sort in ascending order (dir = 1)
    sort(arr, N, 1);

    std::cout << "Sorted array (ascending): ";
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // Re-initialize array for descending sort example
    arr = {3, 7, 4, 8, 6, 2, 1, 5};
    std::cout << "Original array (for descending sort): ";
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // Sort in descending order (dir = 0)
    sort(arr, N, 0);

    std::cout << "Sorted array (descending): ";
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}