kusort.c

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

extern void bitsort_recursive(unsigned int *old_seq, unsigned int *new_seq, size_t size, size_t maxbit);

void bitsort_recursive(unsigned int *old_seq, unsigned int *new_seq, size_t size, size_t maxbit)
{
    int i;
    size_t l_pos;
    size_t r_pos;
    int t;

    maxbit -= 1;
    if (maxbit) {
        t = 1 << maxbit;
        l_pos = 0;
        r_pos = size - 1;
        for (i = 0; i < size; ++i) {
            if (old_seq[i] & t) {
                new_seq[r_pos] = old_seq[i];
                r_pos--;
            } else {
                new_seq[l_pos] = old_seq[i];
                l_pos++;
            }
        }
        if (l_pos > 0) {
            bitsort_recursive(new_seq, old_seq, l_pos, maxbit); /* left */
        }
        if (size - l_pos > 0) {
            bitsort_recursive(new_seq + l_pos, old_seq + l_pos, size - l_pos, maxbit); /* right */
        }
    }
}

void bitsort(unsigned int *seq, size_t size, size_t maxbit)
{
    int i;
    unsigned int *old_seq;
    unsigned int *new_seq;

    old_seq = (unsigned int*)malloc(sizeof(unsigned int) * size);
    new_seq = (unsigned int*)malloc(sizeof(unsigned int) * size);
    memcpy(old_seq, seq, sizeof(unsigned int) * size);
    bitsort_recursive(old_seq, new_seq, size, maxbit);
    if (maxbit % 2 == 1) {
        for (i = 0; i < size; ++i) {
             printf("%u\n", old_seq[i]);
        }
    } else {
        for (i = 0; i < size; ++i) {
             printf("%u\n", new_seq[i]);
        }
    }
    free(old_seq);
    free(new_seq);
}

int main(void)
{
    unsigned int list[] = {3, 1, 4, 15, 9, 255, 254, 128, 127, 89, 7, 9};

    bitsort(list, sizeof(list) / sizeof(unsigned int), sizeof(unsigned int) * 8);

    return 0;
}