Understanding Radix Sort in C

Question

I am using this program here for reference to see how the algorithm is implemented. I understand most of it except this part:

/*
 * update all the buckets. If bucket[8] has 2,
 * then there are 2 elements present till bucket 8
 */
for (i = 1; i < 10; i++)
        bucket[i] = bucket[i] + bucket[i-1];  

I don't understand what the author is doing in that loop. Can someone please explain what is going on ?
And yes, I am using pen-and-paper to see what is going on. Just thought I might clarify that

Answer 1

If you are confused with that line, you can read about counting sort. One of the important things to understand abount radix sort is that it doesn't sort by itself. There is a sub-algorithm that has to be used, and it is often counting sort.

The link you provided does not tell that and it's an important confusion in my opinion. When you read

"During first pass, sort all the data based on the least significant bit"

It doesn't tell how you sort. You could sort with any other stable sort, and the code would change drastically.

All this to say that if this is the only line that you don't understand, you got radix sort figured out. Read about counting sort to understand how it works, and make sure you understand why it's a good choice as a subroutine of radix sort.

Answer 2

This function is taking the cumulative sum, now bucket[i] contains the cumulative sum of itself and all buckets before it. What the comment means is that bucket[8] == 2 would mean that the sum from of buckets 0 to 8 = 2

Edit: Personally I think http://www.youtube.com/watch?v=Nz1KZXbghj8&noredirect=1 has a great radix sort explanation.