C++ Поразрядная сортировка

[vimexgames]

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

typedef struct slist_ { 
  long val;
  struct slist_ *next; 
} slist;
 
// функция сортировки возвращает указатель на начало отсортированного списка 
slist *radix_list(slist *l, int t) {
  //  t - разрядность (максимальная длина числа) 
  int i, j, d, m=1;
  slist *temp, *out, *head[10], *tail[10];
  out=l;
 
  for (j=1; j<=t; j++) { 
    for (i=0; i<=9; i++)
      head[i] = (tail[i]=NULL);
 
    while ( l != NULL ) {
      d = ((int)(l->val/m))%(int)10;
      temp = tail[d];
      if ( head[d]==NULL ) head[d] = l;
      else temp->next = l;
      temp = tail[d] = l;
      l = l->next;
      temp->next = NULL;
    }
    for (i=0; i<=9; i++)
      if ( head[i] != NULL ) break;
    l = head[i];
    temp = tail[i];
    for (d=i+1; d<=9; d++) {
      if ( head[d] != NULL) { 
        temp->next = head[d];
        temp = tail[d];
      }
    }
    m*=10;
  }
  return (out);
}