Поразрядный метод сортировки обладает следующими особенностями:

Во-первых, данный метод совсем не использует сравнений сортируемых элементов.
Во-вторых, ключ, по которому происходит сортировка, необходимо разделить на части, разряды ключа. Например, слово можно разделить по буквам, число - по цифрам...
До сортировки необходимо знать два параметра: k и m, где

k - количество разрядов в самом длинном ключе
m - разрядность данных: количество возможных значений разряда ключа

При сортировке русских слов m = 33, так как буква может принимать не более 33 значений. Если в самом длинном слове 10 букв, k = 10.
Аналогично, для для шестнадцатеричных чисел m=16, если в качестве разряда брать цифру, и m=256, если использовать побайтовое деление.
Эти параметры нельзя изменять в процессе работы алгоритма.

Поразрядная сортировка беззнаковых целых чисел

На хранение каждого из базовых типов выделяется строго определенное количество байт. Как правило, распределение такое:
unsigned char- 1 байт,
unsigned short int - 2 байта,
unsigned long int- 4 байта.
При этом большинство процессоров использует обратный порядок записи: от младшего байта к старшему. Так число типа short int i = 669110 = 0x1A23 непосредственно в памяти хранится так:

Рис. 1.  

Если это число имеет тип long int, то под него выделяется 4 байта: long int i = 669110 = 0x00001A23.

Рис. 2.  

В конце расположены ведущие нули. Таким образом, необходимо провести сортировку от начала числа к концу. Каждый байт может принимать в общем случае 256 значений: m=256.

// Создать счетчики.
// data-сортируемый массив, counters-массив для счетчиков, N-число элементов в data
template<class T>
void createCounters(T *data, long *counters, long N) {
    // i-й массив count расположен, начиная с адреса counters+256*i
memset( counters, 0, 256*sizeof(T)*sizeof(long) ); 
uchar *bp = (uchar*)data;
uchar *dataEnd = (uchar*)(data + N);
ushort i;
while ( bp != dataEnd ) {
// увеличиваем количество байт со значением *bp
// i - текущий массив счетчиков
for (i=0; i<sizeof(T);i++)
counters[256*i + *bp++]++;
}
}
// Функция radixPass принимает в качестве параметров
// номер байта Offset,
// число элементов N, 
// исходный массив source, 
// массив dest, куда будут записываться числа, отсортированные по байту Offset
// массив счетчиков count, соответствующий текущему проходу.
template<class T>
void radixPass (short Offset, long N, T *source, T *dest, long *count) {
    // временные переменные
T *sp;
long s, c, i, *cp;
uchar *bp;
    // шаг 3
s = 0; // временная переменная, хранящая сумму на данный момент
cp = count;
for (i = 256; i > 0; --i, ++cp) {
c = *cp;
*cp = s;
s += c;
}
// шаг 4
bp = (uchar *)source + Offset;
sp = source;
for (i = N; i > 0; --i, bp += sizeof(T) , ++sp) {
cp = count + *bp;
dest[*cp] = *sp;
++(*cp);
}
}

Процедура сортировки заключается в осуществлении sizeof(T) проходов по направлению от младшего байта к старшему.
// сортируется массив in из N элементов
// T - любой беззнаковый целый тип
template<class T>
void radixSort (T* &in, long N) {
T *out = new T[N];
long *counters = new long[sizeof(T)*256], *count;
createCounters(in, counters, N);
for (ushort i=0; i<sizeof(T); i++) {
count = counters + 256*i;         // count - массив счетчиков для i-го разряда
//f ( count[0] == N ) continue;    // (*** оптимизация)
radixPass (i, N, in, out, count); // после каждого шага входной и 
swap(in, out);                    // выходной массивы меняются местами
}
                          // по окончании проходов
delete out;           // вся информация остается во входном массиве.
delete counters;
}

Обратим внимание, что если число проходов нечетное(например, T=unsigned char), то из-за перестановки swap() реально уничтожается исходный массив, а указатель in приобретает адрес out. Об этом следует помнить, используя указатели на сортируемый массив во внешней программе.
Такая организация процедуры также является прототипом для сортировки строк: достаточно сделать проходы radixPass от последней буквы к первой.

Эффективность поразрядной сортировки

Рост быстрой сортировки мы уже знаем: O(nlogn). Судя по оценке, поразрядная сортировка растет линейным образом по n, так как k,m - константы. Также она растет линейным образом по k - при увеличении длины типа(количества разрядов) соответственно возрастает число проходов. Однако, в последний пункт реальные условия вносят свои коррективы.
Дело в том, что основной цикл сортировки по i-му байту состоит в движении указателя uchar* bp шагами sizeof(T) по массиву для получения очередного разряда. Когда T=char, шаг равен 1, T=short - шаг равен 2, T=long - шаг равен 4... Чем больше размер типа, тем менее последовательный доступ к памяти осуществляется, а это весьма существенно для скорости работы. Поэтому реальное время возрастает чуть быстрее, нежели теоретическое.
Кроме того, поразрядная сортировка уже по своей сути неинтересна для малых массивов. Каждый проход содержит минимум 256 итераций, поэтому при небольших n общее время выполнения (n+m) определяется константой m=256.
Поведение неестественно, так как проходы выполняются полностью, вне зависимости от исходного состояния массива. Поразрядная сортировка является устойчивой.