Why does counting sort copy the input elements?
They do not need to do it this way, but they might have found it more elegant.

Their idea is not:


  Put every element j in 0..k-1 into b exactly c[j] times.


But rather:


  Use the counts to compute the position of every a[i] in b.


That is what the second loop is for: it subsequently computs the offsets for the block of elements i in b.
(The should use j here to avoid confusing, but well.)

As KWillets notes, the latter idea lends itself¹ better to sorting more complex data, say objects, by an integer key; then you would need to copy the references in proper order. Note how it is even stable!

On the other hand, if you do not need resp. make use of this, I expect the first idea to be much more efficient in practice: observe how the second implementation makes non-sequential accesses to arrays b and c which may cause a lot more cache misses than the alternative.




The given implementation can only sort integer arrays, of course.