Attempts at a Radix Sorting algorithm

main.cpp

#include <iostream>
#include "radix.h"

using namespace std;

int main() {
    RadixSort rs;

    int a[] = {130372, 119068, 186654, 129168, 76632, 42031, 46162, 119045, 14752, 193735, 157498, 126817, 142080, 147393, 86974, 127750, 34873, 87204, 65382, 113653, 192509, 121459, 78682, 185678, 79606, 37281, 197370, 99172, 116931, 70106, 10163, 61512, 173365, 16677, 26241, 96800, 56034, 68555, 41906, 38607, 191949, 88513, 156681, 63427, 94429, 48383, 126838, 11463, 72520, 12490 };

    Elem* list = new Elem();
    Elem* it = list;
    for (int i = 0; i < 19; i++) {
        it->key.i = a[i];
        it->data = NULL;
        it->next = new Elem();
        it = it->next;
    }
    it->key.i = a[19];
    it->data = NULL;
    it->next = NULL;

    list = rs.sort(list, RadixSort::kUnsigned);

    for (it = list; it != NULL; it = it->next) {
        cout << it->key.i << endl;
    }

    return 0;
}

radix.cpp

#include "radix.h"

RadixSort::RadixSort() {
    memset(heads, 0, sizeof(Elem*)*256);
    memset(tails, 0, sizeof(Elem*)*256);
}

Elem* RadixSort::sort(Elem* in, unsigned int flags) {
    Elem* res = in;

    if (in && in->next) {
        list = in;

        char key;
        Elem* it;

        for (int i = 0; i < 4; i++) {
            it = list->next;
            while (it != NULL) {
                key = (list->key.i >> i) & 0xFF;
                if (tails[key])
                    tails[key]->next = list;
                else
                    heads[key] = list;

                list->next = NULL;
                tails[key] = list;
                list = it;
                it = it->next;
            }
            collapse();
        }

        if (flags & kSigned) {
            unpackSigned();
        } else if (flags & kFloat) {
            unpackFloat();
        }

        if (flags & kReverse) {
            reverse();
        }

        res = list;
    }

    return res;
}

void RadixSort::collapse() {
    Elem* h = NULL;
    Elem* t = NULL;

    for (int i = 0; i < 256; i++) {
        if (heads[i]) {
            if (h) {
                t->next = heads[i];
            } else {
                h = heads[i];
            }

            t = tails[i];
        }

        tails[i] = NULL;
        heads[i] = NULL;
    }

    list = h;
}

void RadixSort::reverse() {
    if (list && list->next) {
        Elem* next = list->next;

        list->next = NULL;
        Elem* nnext = NULL;
        while ((nnext = next->next) != NULL) {
            next->next = list;
            list = next;
            next = nnext;
        }
    }
}

void RadixSort::unpackSigned() {
}

void RadixSort::unpackFloat() {
}

radix.h

#include <cstdio>
#include <cstring>

#ifndef _RADIX_H_
#define _RADIX_H_

struct Elem {
    union {
        int i;
        unsigned int u;
        float f;
    } key;

    void* data;

    Elem* next;

    Elem() : data(NULL), next(NULL) { }
};

class RadixSort {
public:
    enum {
        kFloat = 0,
        kSigned = 1,
        kUnsigned = 2,
        kReverse = 4
    };

private:
    Elem* list;
    Elem* heads[256];
    Elem* tails[256];

public:
    RadixSort();

    Elem* sort(Elem* in, unsigned int flags);

protected:
    void collapse();
    void reverse();
    void unpackSigned();
    void unpackFloat();
};

#endif