Radix Sort

Files:  sort.c, short.h

Radix sort works by extracting the values of digits within numbers, and sorting
according to the value of each digit.  Any practical radix (or base) can be
used for extracting the values of digits, although the optimal setting depends
on the properties of the values being sorted.  If the radix used is r, radix
sort uses r `buckets' for sorting data items (one bucket for each digit value 0
to r-1).  Note that inserted order of data items into each bucket is
maintained.  In the source file sort.c, each bucket is implemented as a linked
list, and has a pointer to the head list item and tail list item.  Also, during
sorting, the sequence of data items being sorted is maintained as a linked
list.

We start with a linked list of data items to be sorted.  First, each data item
is removed from the list and is placed into the appropriate bucket according to
the value of its least significant digit.  With all items placed in the
appropriate bucket, the linked list of data items is reconstructed by
concatenating the linked list of each bucket with the next.  The resulting
linked list of data items is sorted according to the value of the least
significant digit.

Using the same process, the list is sorted again, this time using the value of
the second least significant digit, to give a list of data items sorted
according to the value of the two least significant digits.  This process
continues until all digits in the data being sorted have being considered.  The
final result is a sorted linked list of data items.

In the source file, sort.c, the function radix_sort() sorts an array of data
items.  Initially, a copy is made of the array, and a linked list is
constructed corresponding to data items in this duplicate array.  The linked
list items have these fields:
 - a value.
 - a pointer to the position of the corresponding data item in the duplicate
   array.
 - a pointer to the next linked list item.
During the initial scan, the maximum value from the set of data items is
determined, and stored in the variable max_value.  This will be used to
determine when sorting is complete.

During each time the linked list gets sorted, the value of each linked list
item is decreased by dividing it by the radix, with the remainder resulting
from the division being used as the digit value.  The value of max_value is
also decreased by dividing it by the radix.  When max_value reaches zero,
sorting is complete since all digits up to and including the most significant
digit of any data item's value will have been considered.

The final step scans the linked list, and overwrites entries in the original
array using array entries from the duplicate array that are pointed to by each
linked list item.  The result is that data in the original array becomes
sorted.