Radix sort

Radix sort is a sort algorithm that operates in O(n) time. This algorithm was orignally used to sort punched cards in several passes. It has resurfaced as an alternative to other high performance sorting algorithms (like quicksort, heapsort and merge sort) which run in O(n lg n)) time. Its greatest disadvantages are that it usually cannot be made to run in place, so O(n) additional memory space is needed, and that it requires one pass for each symbol of the key, so it is very slow for potentially-long keys.

The radix sort algorithm works as follows:

1. take the least significant digit (or group bits) of each key.
2. sort the list of elements based by that digit, but keep the order of elements with the same digit (this is the definition of a stable sort).
3. repeat the sort with each more significant digit.

An example

Sort the list:
170 45 75 90 2 24 802 66

1. sorting by least significant digit (1s place) gives:
   170 90 2 802 24 45 75 65
2. sorting by next digit (10s place) gives:
   2 802 24 45 67 170 75 90
3. sorting by most significant digit (100s place) gives:
   2 24 45 65 75 90 170 802

Sample radix sort on an array of integers in C

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

struct listnode                               /* a simple linked list data structure */
{                                             /* used for the bucket sort */
   int val;
   struct listnode * next;
};

void sort(int * 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(int); i++)           /* iterate over the bytes in an 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--;
	}
   }
}

THANK YOU FOR WRITING THIS WHOEVER DID!!!