====== Lexikografické třídění ======

<code C++>
#include <iostream>
using namespace std;

const int D = 20;  // delka retezce
const int K = 256; // pocet prihradek

struct Item
{
    char key [D+1]; // retezce ukoncene 0
    Item* next;
};

struct List // prihradka
{
    Item * first;
    Item * last;
};

void clear (List & p)
{
    p.first = nullptr;
    p.last = nullptr;
}

void insertLast (List & p, Item * t)
{
    if (p.first == nullptr)
        p.first = t;
    else
        p.last->next = t;
    p.last = t;
    t->next = nullptr;
}

/*
void join (List & target, List & source)
{
    Item* t = source.first;
    while (t != nullptr)
    {
        Item* nxt = t->next;
        insertLast (target, t);
        t = nxt;
    }
}
*/

void join (List & target, List & source)
{
    if (source.first != nullptr)
    {
        if (target.first == nullptr)
        {
            target.first = source.first;
            target.last = source.last;
        }
        else
        {
            target.last->next = source.first;
            target.last = source.last;
        }
    }
}

List tab [K]; // pole prihradek

List queue; // vstupni a vystupni posloupnost

void sort (int r) // trideni podle r-teho znaku
{
    // vymazat prihradky
    for (int i = 0; i < K; i++) clear (tab [i]);

    // rozhazet do prihradek
    Item* t = queue.first;
    while (t != nullptr)
    {
        int inx = t->key [r]; // cislo prihradky
        Item* nxt = t->next; // uschovat, t->next buze zmeneno
        insertLast (tab [inx], t); // pridat na konec prihradky
        t = nxt;
    }

    // vymazat queue, bude slouzit pro vystup
    clear (queue);

    // sloucit 
    for (int i = 0; i < K; i++)
        join (queue, tab [i]);
}

void lexiSort ()
{
    for (int r = D-1; r >= 0; r--)
        sort (r);
}

void add (const char* s)
{
    Item* t = new Item;
    int len = strlen (s);
    for (int i = 0; i < D; i++)
    {
        if (i < len)
            t->key [i] = s [i];
        else
            t->key [i] = 0;
    }
    t->key [D] = 0;
    insertLast (queue, t);
}

void tisk ()
{
    Item* t = queue.first;
    while (t != nullptr)
    {
        cout << t->key << endl;
        t = t->next;
    }
}

int main()
{
    clear (queue);

    /*
    add ("751");
    add ("123");
    add ("111");
    */

    srand (time (nullptr));
    const int N = 1000;
    for (int i = 1; i <= N; i++)
    {
        int v = (rand () % 1000) + 1000 * (rand () % 1000);
        string s = to_string (v);
        while (s.length () < D) s = '0' + s;
        add (s.c_str ());
    }

    lexiSort ();
    tisk ();

    cout << "O.K." << endl;
}
</code>