Oops - I left this sitting from a couple of nights back and never sent it!!!
Also, if any of you need to catch me today (Wed) and don't already have
an appointment then I still have some time after 3:30.


Answers to some common questions you've sent on the radix sort....

1) So I get 100% for the lsd version but another 25 for also doing msd?
Yes I give 100% for which ever one you do first and an additional 25 bonus
for the 2nd one.  Once you see how to replace the lsd iteration with
the msd recursion the rest is basically the same.

2) my realloc is never getting called
Although its OK for initial debugging you shouldn't malloc all n in each
bin since that uses 256 times more memory than you really need.
You want to malloc less than you expect to need and then realloc gradually
to reach what ever bin sizes are actually required in the specific case.
A little over shoot is fine but a gross overestimate will limit the
size of problems that you can handle on your machine.

3) How do we convert the Radix to a binary mask?
You don't really have to "convert" it to binary but just realize that
if we only use a power of 2 radix then (RADIX-1) will already have the
proper bit pattern to work as a mask.

4) The bins and the array are pointers do I have to use the pointer notation?
You can take advantage of the fact that the compiler lets you use either
pointer or array notation and will do the proper conversion for you.
That is, rather than *(array+i) you can use array[i].

5) Since bin[] is a 1D array how do we put more than one number into a bin?
bin[] is a 1D array of pointers to unsigned integers.  Therefore you have
one dimension that tells you which bin you are using and a 2nd dimension
that follows into the memory that is pointed to so that you can access
the individual numbers there.  That is, you mostly want to use bin
as if it is a 2D array ... bin[][]

6) What is the arithmetic equivalent of shifting left or right?
A left shift is equivalent to multiply by 2 and right shift is div by 2.
However, in this case we are more concerned with using the shifts to
move particular bit fields out of a 32 bit number into position so that
we can mask off a particular number of bits from the right end.

7) What is the meaning of BITS, RADIX and DIGITS again?
I'm using BITS simply as a more convenient way to specify the RADIX.
If BITS is 1 then RADIX is 2.  With the default BITS = 8 then the
ratix is 2 to the 8th which is 256.  DIGITS will be the number of
digits that we would need in the current RADIX to encode a complete
32 bit number.  Notice that if we allowed an arbitrary radix, say 13,
then it would be harder to say how many digits we need and also more
difficult and slower to produce those digits.  We are taking heavy
advantage of the properties of base two numbers here.

8) How much memory should we allocate for each bin and is there a
simple formula for it?
The quick answer is that each bin would be expected to hold n/RADIX
values if everything was perfectly distributed. However, as discussed
in class the random distribution will not produce such a perfect
distribution so you want to allocate and reallocate so that it will
accomodate the actual distribution.  This can be done in many ways.
My suggestion is to initiall malloc some reasonable fraction, say half,
of the number of values you expect in each bin and then let the realloc
do the rest.  When you realloc you don't want to just allocate 1 by
one since reallocation can take a long time. Rather reallocate for some
substantial increase in size.  By substantial I don't just mean to add,
for example, 100 new elements.  It is better to increase by some percentage
relative to your current size so that it will behave reasonably well for
both small and large problems.