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.

- Implement radix sort for sorting in non-decreasing order (that is,
any element is less than or equal to its successor, if any) a list
`L`of natural numbers with maximum`d`digits in the chosen base*k*:`radixSort L d : int list -> int -> int list`, such that the running time for*n*elements is Θ(*n*).**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. - Compare radix sort against merge-sort or quick-sort via
experiments on the
*same*random lists of 0 to 100,000 elements, by increments of 5,000 elements. Plot the running times in*one*diagram and give them in tabular form as well. Indicate how you generated the random lists of each length.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`. - Are the results as expected? Why / Why not?

- SML functions for Question 1 above, in a .sml file, executable
under Moscow ML version 2.01, and documented, in English,
according to the coding
convention of the course.
- Replies, in English, to Questions 2 to 3 above, in a .pdf or .html file.