Radix sort is described in the Dictionary of Algorithms and Data Structures and in the Introduction to Algorithms textbook (errata), on pages 170 to 173 (you need not read up anything about counting sort, nor use a sorting algorithm to classify the numbers into the bins). You can choose any number k of bins (or buckets), corresponding to the base in which your algorithm views the given numbers, but you must indicate that base in your specification.
The additional knowledge of the maximal number d of digits of the n numbers in the list allows the design of such linear-time Θ(n) sorting algorithms (when d is a constant and k = O(n)). This beats, in theory, the O(n lg n) running time of comparison-based sorting algorithms that are not given any such knowledge.
The objective of this assignment is to assess the subtleties in efficiently implementing radix sort for lists and properly examining its actual efficiency.
Example: radixSort [9821, 5674, 7890, 1234, 638] 4 = [638, 1234, 5674, 7890, 9821], assuming the algorithm has k = 10 bins, because all the n = 5 given numbers have maximum d = 4 digits in base k = 10. Use d = 14 if viewing those numbers in base k = 2 and thus using only k = 2 bins.
To generate a random list, use Random.rangelist (minimalElement, maximalElement) (numberOfElements, Random.newgen()). The interval between the smallest and largest possible values of a random list should be at least 100 times larger than the number of elements of that list, otherwise there will be too many duplicates in the generated lists. Many duplicates would mean that one examines an extreme case rather than a general, random case.
To measure a running time, use the function timeIt in the file ranTime.sml, which takes a function f and an argument a and returns the running time for f applied to a.
To plot the data of a file called file.data, use the command plot "file.data" with lines in gnuplot. If you have several files, then write plot "file1.data" with lines, "file2.data" with lines instead. If you want to produce a Postscript file, write set terminal postscript and set output "file.ps" before running the plot command again. A Unix command for converting Postscript to PDF is ps2pdf.