Radix sort has resurfaced as an alternative to other high performance sorting algorithms (like quicksort, heapsort and merge sort) which require O(n lg n)) comparisons, where n is the number of items to be sorted. These other algorithms are able to sort with respect to more complicated orderings than lexicographic, but this is of little importance in many practical applications.
If the size of the possible key space is proportional to the number of items, then each key will be lg n symbols long, and radix sort uses O(n lg n)) time in this case.
The greatest disadvantages or radix sort 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.
Radix sort uses the following sorting order: short keys come before longer keys, and keys of the same length are sorted lexicographically. This coincides with the normal order of numbers, if the numbers are represented as digit strings.
The radix sort algorithm works as follows:
The sort in step 2 is usually done using [bucket sort]?, which works since there are only finitely many digits.
Sort the list:
170, 45, 75, 90, 2, 24, 802, 66
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 */ int 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--; } } }