Radix sort/Talk

THANK YOU FOR WRITING THIS WHOEVER DID!!!

---

Does the sample implementation given depend on the endianness used by the computer? I'm not quite sure what exactly the >> operator does. --AxelBoldt

The value of x >> y is floor(x / 2^y), provided x and y are non-negative, and y is not too big. So it doesn't depend on endianness in this case. But if x is negative, then the value is undefined, so this is a problem. Another problem with the code in the article is that it assumes that CHAR_BIT is 8. --Zundark, 2001 Dec 11

So maybe we should make them unsigned ints to take care of the sign issue? Is there a clean way to deal with the CHAR_BIT thingy?

I think we should probably have an implementation that deals with keys that are (arbitrary length) strings, since that seems to be the more interesting case. --AxelBoldt

I changed the int array to unsigned. The CHAR_BIT thing is more problematic, so I just added a note pointing it out. On most compilers for desktop computers CHAR_BIT is 8, so this isn't too bad a restriction. --Zundark, 2001 Dec 11

Having looked at it more closely, I see that it has more serious problems than those mentioned above, so I've removed it until it gets fixed. (I added a copy below.) --Zundark, 2001 Dec 11

---

Sample radix sort of an array of integers

This sample implementation is written in the C programming language.

/*
 * 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--;
	}
   }
}

---