#include <stdio.h>
#include <assert.h>
#include <time.h>
#include <stdlib.h>

#define TESTSIZE ((size_t)( 1<<25 ))

void comp_and_swap(int* data, size_t i, size_t j) {
    if(data[i] > data[j]) {
        int tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }
}

void sort_step(int* data, size_t N, size_t shift, unsigned int step) {
    for(size_t i = 0; i < N; i+=2*shift) {
        for(size_t j = i; j < i+shift; j++) {
            if( (i/step)%2 == 0 ) {
                comp_and_swap(data, j, j+shift);
            } else {
                comp_and_swap(data, j+shift, j);
            }
        }
    }
}

void sort_step2(int* data, size_t N, size_t step) {
    for(size_t i = step; i > 1; i/=2) {
        sort_step(data, N, i/2, step);
    }
}

void bitonic_sort(int* data, size_t N) {
    for(size_t step = 2; step <= N; step*=2) {
        printf("Pack: %d\n", step);
        sort_step2(data, N, step);
    }
}

int main( int argc, char *argv[] ) {
    srand(time(NULL));

    int* data = malloc(sizeof(int) * TESTSIZE);
    for(size_t i = 0; i < TESTSIZE; i++) {
        data[i] = rand() % 1000;
    }

    bitonic_sort(data, TESTSIZE);

    for(size_t i = 0; i < TESTSIZE-1; i++) {
        assert(data[i] <= data[i+1]);
    }

	return 0;
}