Sorting using radix sort

Question

I was reading radix sort from this site I am confused in the 3rd for loop:

for (i = n - 1; i >= 0; i--) {
    output[freq[(arr[i] / place) % range] - 1] = arr[i];
    freq[(arr[i] / place) % range]--;
}

Why did they start it from the end as when I tried to start it from 0, it gives me the wrong answer? Any explanation or solution would be appreciated.

Answer 1

Because freq contains the cumulative number of elements in each position in the range. That is, for a range of i=0-9, freq[i] contains the number of digits that are placed on positions 0, ..., i.

The algorithm uses freq to keep track of how many items it needs to draw from initial array to the output array for each position.

Assuming 10,21,17,34,44,11,654,123 as input, running count-sort for first insignificant digit:

0: 10
1: 21 11
2:
3: 123
4: 34 44 654
5:
6:
7: 17
8:
9: 

freq would be as:

0: 1
1: 3
2: 3
3: 4
4: 7
5: 7
6: 7
7: 8
8: 8
9: 8

So, the array becomes 10,21,11,123,34,44,654,17.

You need to loop backwards to keep the original order of numbers with the same digit, because how the freq is built. Suppose you want to place 34 to its right place on the output. According to the freq array, if loop forward, you would place it on the 7th position which is incorrect. If you loop backwards, you have already placed 654 and 44 before reaching 34, so freq[4]=5 by then which is the correct place.