$ cat RadixSort.cpp
/*---------------------------------------------------------------------------
 * 20031117 - originally written
 *---------------------------------------------------------------------------
 */

#include <assert.h>
#include <io.h>

#pragma pack(push,1)
struct TxnRec {
    TxnRec  *next;
    char     key[8];

    // The rest of the record...
};

TxnRec * root;
TxnRec * last;

// Read the records, chaining them together
void read_transactions(const char *FName) {
    // Read and format the record
    TxnRec *p = get_transaction(IFH);
    root = last = p;
    while (p = get_transaction(IFH)) {
        last->next = p;
        last = p;
    }
}

void sort_records() {
    assert(root);

    // heads & tails of our buckets
    static TxnRec *multiroot[256];
    static TxnRec *multitail[256];

    // Radix sort from rightmost byte to leftmost
    for (int i=7; i>=0; --i) {

        // Clear traces of any prior sort(s)/pass(es)
        memset(multiroot, 0, sizeof(multiroot));
        memset(multitail, 0, sizeof(multitail));

        // Break the chain into 256 chains based on the key position
        TxnRec *p = root;
        while (p) {
            // Keep a handle on the next record to process
            TxnRec *next = p->next;

            // Detach it from the chain
            p->next=0;

            unsigned char c = p->key[i];
            if (!multiroot[c]) {
                // First item in bucket
                multiroot[idx] = p;
                multitail[idx] = p;
            }
            else {
                // Add it to the end
                multitail[idx]->next = p;
                multitail[idx] = p;
            }
            p = next;
        }

        // And then stitch them together end-to-end
        root = 0;
        TxnRec *tail = 0;
        for (int j=0; j<256; j++) {
            if (multiroot[j]) {
                if (!root) {
                    root = multiroot[j];
                    tail = multitail[j];
                }
                else {
                    tail->next = multiroot[j];
                    tail = multitail[j];
                }
            }
        }
    }
}