bitonic_sort.c

/* Bitonic sort.

Compile and run with gcc ./bitonic_sort.c -O3 -o program; ./program

Reference:

Wikipedia - Bitonic Sort
https://en.wikipedia.org/wiki/Bitonic_sorter

*/
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

const int N = 32768;
int s_arr[N] = {0};

void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void bitonic_sort4(int *arr, int is_ascending) {
    int tmp[4] = {
        arr[0], arr[2], 
        arr[1], arr[3]};
    if (is_ascending) {
        if (tmp[0] > tmp[1])
            swap(&tmp[0], &tmp[1]);
        if (tmp[2] > tmp[3])
            swap(&tmp[2], &tmp[3]);
    } else {
        if (tmp[0] < tmp[1])
            swap(&tmp[0], &tmp[1]);
        if (tmp[2] < tmp[3])
            swap(&tmp[2], &tmp[3]);
    }
    int tmp2[4] = {
        tmp[0], tmp[2], tmp[1], tmp[3]};
    if (is_ascending) {
        if (tmp2[0] > tmp2[1])
            swap(&tmp2[0], &tmp2[1]);
        if (tmp2[2] > tmp2[3])
            swap(&tmp2[2], &tmp2[3]);
    } else {
        if (tmp2[0] < tmp2[1])
            swap(&tmp2[0], &tmp2[1]);
        if (tmp2[2] < tmp2[3])
            swap(&tmp2[2], &tmp2[3]);
    }
    for (int i = 0; i < 4; i++)
        arr[i] = tmp2[i];
}

void sort4(int *arr, int is_ascending) {
    if (arr[0] < arr[1])
        swap(&arr[0], &arr[1]);
    if (arr[3] < arr[2])
        swap(&arr[2], &arr[3]);
    bitonic_sort4(arr, is_ascending);
}

void bitonic_sort(int *arr, int n, int is_ascending_order);

void sort(int *arr, int n, int is_ascending_order) {
    if (n == 4) {
        sort4(arr, is_ascending_order);
    } else if (n == 2) {
        if (arr[1] < arr[0])
            swap(&arr[1], &arr[0]);
    } else {
        sort(arr, n/2, 1);
        sort(&arr[n/2], n/2, 0);
        bitonic_sort(arr, n, is_ascending_order);
    }
}

void bitonic_sort(int *arr, int n, int is_ascending_order) {
    if (n == 4) {
        bitonic_sort4(arr, is_ascending_order);
        return;
    }
    int *tmp = malloc(n*sizeof(int));
    int *tmp2 = malloc(n*sizeof(int));
    for (int i = 0; i < n/2; i++) {
        tmp[2*i] = arr[i];
        tmp[2*i + 1] = arr[i + n/2];
    }
    for (int i = 0; i < n/2; i++) {
        if (is_ascending_order) {
            if (tmp[2*i + 1] < tmp[2*i])
                swap(&tmp[2*i + 1], &tmp[2*i]);
        } else {
            if (tmp[2*i + 1] > tmp[2*i])
                swap(&tmp[2*i + 1], &tmp[2*i]);
        }
    }
    for (int i = 0; i < n/2; i++) {
        tmp2[i] = tmp[2*i];
        tmp2[i + n/2] = tmp[2*i + 1];
    }
    bitonic_sort(tmp2, n/2, is_ascending_order);
    bitonic_sort(&tmp2[n/2], n/2, is_ascending_order);
    for (int i = 0; i < n; i++)
        arr[i] = tmp2[i];
    free(tmp);
    free(tmp2);
}

int main() {
    for (int i = 0; i < N; i++) {
        srand(time(NULL) + i + rand());
        int val = rand() % 100;
        s_arr[i] = val;
        // printf("%d\n", s_arr[i]);
    }
    // puts("");
    sort(s_arr, N, 1);
    for (int i = 0; i < N-1; i++) {
        if (s_arr[i + 1] < s_arr[i]) {
            printf("Not properly sorted: array at "
                    "index %d with value %d less than array at index %d"
                    " with values %d.\n",
                    i + 1, s_arr[i + 1], i, s_arr[i]);
        }
    }
    return 0;
}