History of Radix sort/Talk

Sample radix sort of an array of integers

 /*
  * This implementation sorts one byte at a time, so 32 bit integers get sorted in 4 passes.
  * It uses a simplified bucket sort to sort on each byte, which requires O(n) memory.
  * It assumes that CHAR_BIT is 8.
  */
 
 struct listnode                               /* a simple linked list data structure */
 {                                             /* used for the bucket sort */
    unsigned val;
    struct listnode * next;
 };
 
 void sort(unsigned * array, int length)
 {
    int i, j;
    unsigned char key;              
    struct listnode nodes[length];             /* an array of preallocated listnodes */
    struct listnode * buckets[0x100];          /* the buckets for the bucket sort */
    
    memset(buckets, 0, 0x100 * sizeof(struct listnode *)); /* zero the memory */
    
    for(i = 0; i < sizeof(unsigned); i++)      /* iterate over the bytes in an unsigned int */
    {
       for(j = 0; j < length; j++)             /* iterate over the array */
       {
 	 key = (char)((array[j] >> (i * 8)) & 0xFF); /* grab the byte */
 
          nodes[j].val = array[j];             /* put the byte in the bucket */
 	 nodes[j].next = buckets[key];
 	 buckets[key] = &(nodes[j]);
       }
       
       j = length - 1;
       for(key = 0xFF; key >= 0; key--)        /* loop over the buckets */
         while(buckets[key] != 0)
         {
            array[j] = buckets[key]->val;      /* pull the values out of the buckets */
 	   buckets[key] = buckets[key]->next; /* and put them back in the array */
 	   j--;
 	}
    }
 }