A: Kantor Ilia
  
  Пусть имеем максимум по k байт в каждом ключе ( хотя за элемент
 сортировки вполне можно принять и что-либо другое, например слово -
 двойной байт, или буквы, если сортируются строки). k должно быть
 известно заранее, до сортировки.

 Разрядность данных ( количество возможных значений элементов ) - m,
также должна быть известна заранее и постоянна.
                                                               
  Если мы сортируем слова, то элемент сортировки - буква. m = 33.
 Если в самом длинном слове 10 букв, k = 10.

 Обычно мы будем сортировать данные по ключам из k байт, m=256.

----------------------------------------------------------------------
  Пусть у нас есть массив source из n элементов по одному байту в каждом.

 Для примера можете выписать на листочек массив 
 source[1..7] = { 7,9,8,5,4,7,7 }, и проделать с ним все операции,
 имея в виду m=9. n здесь, очевидно, равно 7.
                                                            
     I. Составим таблицу распределения. В ней будет m ( = 256 ) значений и
заполняться она будет так:

for ( i = 0 ; i < 255; i++ ) distr[i]=0;
for ( i = 0 ; i < n ; i++ ) distr[source[i]] = distr[[i]] + 1;

  Для нашего примера будем иметь distr = { 0,0,0,0,1,1,0,3,1,1 },
 то есть i-ый элемент distr[] - количество ключей со значением i.

     Заполним таблицу индексов:

int index[256];
index [0]=0;
for ( i = 1 ; i < 255; i++ ) index[i]=index[i-1]+distr[i-1];

     В index[i] мы поместили информацию о будущем количестве символов в
отсортированном массиве до символа с ключом i. 
     Hапример, index[8] = 5 : имеем 4, 5, 7, 7, 7, 8.

  А теперь восстановим уже отсортированный массив sorted размера n:

for ( i = 0; i < n ; i++ )
     {
      sorted[ index[ source[i] ] ]=source[i];
// попутно изменяем index уже вставленных символов, чтобы
// одинаковые ключи шли один за другим:
      index[ source[i] ] = index[ source[i] ] +1;
     }

 Проще всего понять, почему все получается, можно проделав все операции
на бумаге.
	 
     Итак, мы научились за O(n) сортировать байты. А от байтов до строк
и чисел - 1 шаг. Пусть у нас в каждом числе - k байт.

  Будем действовать в десятичной системе и сортировать обычные числа 
 ( m = 10 ).

      сначала они в      сортируем по          по разряду
       беспорядке:      младшему разряду:        левее:     и еще раз,:
           523                523                523         088
           153                153                235         153
           088                554                153         235
           554                235                554         523
           235                088                088         554
                               /|\               /|\        /|\
                                |                 |          |								
    Вот мы и отсортировали массив за O(kn) шагов. Если количество
возможных различных ключей ненамного превышает общее их число, то
поразрядная сортировка оказывается гораздо быстрее даже 'быстрой
сортировки' !

     Распределяющая сортировка, требует O(n) дополнительной памяти.

 Пример(учебный) реализации radixsort на Си++ для long int'ов.
 
 #include <iostream.h>
 #include <stdlib.h>
 #include <string.h>

 void radix (int byte, long N, long *source, long *dest)
 {
  // *source - входной массив,
  // *dest - отсортированный.
  long count[256];    // вообще говоря, можно обойтись 
  long index[256];    // одним массивом count[]
  
  memset (count, 0, sizeof (count));
  for ( int i=0; i<N; i++ ) count[((source[i])>>(byte*8))&0xff]++;
  index[0]=0;
  for ( i=1; i<256; i++ ) index[i]=index[i-1]+count[i-1];
  for(i=0;i<N;i++) dest[index[((source[i])>>(byte*8))&0xff]++]=source[i];
 }

 void radixsort (long *source, long *temp, long N)
 {
  // Сортируем по всем 4 разрядам
  radix (0, N, source, temp);
  radix (1, N, temp, source);
  radix (2, N, source, temp);
  radix (3, N, temp, source);
 }

 void make_random (long *data, long N)
 {
  for ( int i=0; i < N; i++ ) data[i]=rand()|(rand()<<16);
 }

 long data[10000];
 long temp[10000];

 void main (void)
 {
  make_random(data, 10000);
  radixsort (data, temp, 10000);
  for ( int i=0; i<100; i++ ) cout << data[i] << '\n';
 }
 
 Примечания.
 
1.  К сожалению, или к счастью, единица информации в современной 
 технике способна принимать лишь 2 значения: 1 и 0.
  А значит, любые компьютерные данные тоже могут принимать 
 ограниченное количество значений, так как состоят из некоторого 
 числа битов ;-)). 
  Таким образом, распределяющая сортировка потенциально применима
 где угодно. Другое дело, что если разрядность данных большая 
 по сравнению с общим количеством элементов, то скорость работы
 оставит желать много лучшего.

2. Алгоритм, описанный выше, очевидно, требует O(n) памяти.
Существует похожий алгоритм, использующий лишь O(logn).
  Модифицированная Radix Sort:
Будем сортировать по каждой позиции символа 'на месте', начиная справа:
сначала сортируем по первой позиции, затем к каждой части массива,
относящейся к одному и тому же значению, рекурсивно 
применяем ту же процедуру и т.д.

 Этот вариант называется 'Radix exchange sort' и 
представляет собой скорее разновидность QuickSort. 
 Hа мой взгляд, она объединяет больше плохих черт обоих методов,
нежели хороших, но вполне может пригодиться в какой-то ситуации.

>  Существует вариант распределяющей сортировки для списков,
> каждый элемент которых принимает конечное множество значений.
> Он даже проще в реализации, понимании и использовании.

Предположим, что элементы линейного списка В есть Т-разрядные
положительные десятичные числа D(j,n) - j-я справа цифра в десятичном 
числе n>=0, т.е. D(j,n)=floor(n/m)%10, где m=10^(j-1).
 (floor - округление в меньшую сторону)
 Пусть В0,В1,...,В9 - вспомогательные списки (карманы), вначале пустые. 
Для реализации распределяющей сортировки выполняется процедура, 
состоящая из двух процессов, называемых распределение и сборка 
для j=1,2,...,T. 

PАСПРЕДЕЛЕHИЕ 
заключается в том, что элемент Кi (i=1,N) из В добавляется как 
последний в список Bm, где m=D(j,Ki), и таким образом получаем 
десять списков, в каждом из которых j-тые разряды чисел одинаковы и 
равны m. 

СБОРКА 
объединяет списки В0,В1,...,В9 в этом же порядке, 
образуя один список В.
 
> Число карманов - количество возможных значений элемента списка.

Исходный список можно сделать односвязный, а сортировку организовать так,
чтобы для карманов В0,В1,...,В9 не использовать дополнительной памяти, т.е
элементы списка не перемещать, а с помощью перестановки указателей 
присоединять их к тому или иному карману. 

В представленной ниже программе функция pocket реализует распределяющую 
сортировку связанного линейного списка (указатель q), в котором содержатся
Т-разрядные десятичные положительные числа, без использования 
дополнительной памяти;
в функции a[i], b[i] указывают соответственно на первый и на последний 
элементы кармана Bi. 

/*  распределяющая  сортировка  списка    */
#include <stdlib.h>
#include <stdio.h>
	 
typedef struct SP1_ { 
   long val;
   struct SP1_ *next; 
} SP1;

 /*    функция сортировки возвращает указатель на начало
        отсортированного списка      */
SP1 *pocket(SP1 *q,int t) {
    /* t - разрядность (максимальная длина числа) */
   int i,j,k,m=1;
   SP1 *r, *gg, *a[10], *b[10];
   gg=q;
   for(j=1;j<=t;j++) { 
       for(i=0;i<=9;i++) a[i]=(b[i]=NULL);
       while(q!=NULL) {
           k=((int)(q->val/m))%(int)10;
           r=b[k];
           if (a[k]==NULL) a[k]=q; else r->next=q;
           r=b[k]=q;
           q=q->next;
           r->next=NULL;
       }
       for(i=0;i<=9;i++) if (a[i]!=NULL) break;
       q=a[i];
       r=b[i];
       for(k=i+1;k<=9;k++)
           if(a[k]!=NULL) { 
	       r->next=a[k];
               r=b[k];
           }
       m=m*10;
       }
   return (gg);
}

   /* Тестовая программа */	 
void main() {
   int i;
   SP1 *q, *r;
   /* Это будем сортировать */
   long a[14]={ 0,7,8,3,52,14,16,18,15,13,42,30,35,26 };

   q=(SP1 *)malloc(sizeof(SP1));
   q->val=a[0];
   r=q;
   for(i=1;i<14;i++) {     /*  формирование списка  */
         r->next=(SP1 *)malloc(sizeof(SP1));
         r->next->val=a[i];
         r=r->next;
   }
   r->next = NULL;

   /* Список сформирован, q указывает на начало */
    
   r=pocket(q,2);  /* Запускаем сортировку */
   printf("\nresult:\n");          /*  печать результатов   */
   while (r!=NULL) {
      printf(" %d",r->val);
      r=r->next;
   }
}