CPU Bitonic Sort

BitonicSort.c

// sorts an array in ascending order (arraySize muste be a power of two)
void BitonicSort(uint32_t *array, uint32_t arraySize)
{
    for (uint32_t d2 = 1u; d2 < arraySize; d2*= 2u) {
        for (uint32_t d1 = d2; d1 >= 1u; d1/= 2u) {
            const uint32_t mask = (0xFFFFFFFEu * d1);

#pragma omp parallel for
            for (uint32_t i = 0; i < (arraySize / 2); ++i) {
                const uint32_t i1 = ((i << 1) & mask) | (i & ~(mask >> 1));
                const uint32_t i2 = i1 | d1;
                const uint32_t t1 = array[i1];
                const uint32_t t2 = array[i2];
                const uint32_t min = t1 < t2 ? t1 : t2;
                const uint32_t max = t1 < t2 ? t2 : t1;

                if ((i & d2) == 0) {
                    array[i1] = min;
                    array[i2] = max;
                } else {
                    array[i1] = max;
                    array[i2] = min;
                }
            }
        }
    }
}