radix.cpp

struct Node {
    Node() : next{0}, value{0}, head{true}
    { }
    Node(int val, Node* next = 0) : next{next}, value{val}, head{false}
    { }

    ~Node() {
        if (next)
            delete next;
    }

    Node* pushNode(int val)
    {
        if (this->next)
            delete next;
        this->next = new Node(val);
        return this->next;
    }

    void popNode()
    {
        if (this->next) {
            Node* tmp = this->next->next;
            this->next->next = 0;
            delete this->next;
            this->next = tmp;
        }
    }

    Node* next;
    int value;
    bool head;
};

void countSort(int *arr, int size, int exp)
{
    Node* heads[10];
    Node* tails[10];
    for (int i = 0; i < 10; ++i) {
        heads[i] = new Node{};
        tails[i] = heads[i];
    }
    for (int i = 0; i < size; ++i) {
        int index = (arr[i] / exp) % 10;
        // remainder can be negative
        if (index < 0)
            index += 10;
        tails[index] = tails[index]->pushNode(arr[i]);
    }
    int current = 0;
    for (int i = 0; i < 10; ++i) {
        while (heads[i]->next) {
            arr[current] = heads[i]->next->value;
            current += 1;
            heads[i]->popNode();
        }
    }
    for (int i = 0; i < 10; ++i)
        delete heads[i];
}

int max(int *arr, int size)
{
    int max = arr[0];
    for (int i = 1; i < size; ++i)
        if (arr[i] > max)
            max = arr[i];
    return max;
}

void radixSort(int *arr, int size)
{
    int maxVal = max(arr, size);

    for (int exp = 1; (maxVal / exp) > 0; exp *= 10)
        countSort(arr, size, exp);
}