[SOLVED] Counting Sort - Why go in reverse order during the insertion?

Counting Sort - Why go in reverse order during the insertion?

I was looking at the code for Counting Sort on GeeksForGeeks and during the final stage of the algorithm where the elements from the original array are inserted into their final locations in the sorted array (the second-to-last for loop), the input array is traversed in reverse order.

I can't seem to understand why you can't just go from the beginning of the input array to the end, like so :

for i in range(len(arr)): 
        output_arr[count_arr[arr[i] - min_element] - 1] = arr[i] 
        count_arr[arr[i] - min_element] -= 1

Is there some subtle reason for going in reverse order that I'm missing? Apologies if this is a very obvious question. I saw Counting Sort implemented in the same style here as well.

Any comments would be helpful, thank you!

Solution

Stability. With your way, the order of equal-valued elements gets reversed instead of preserved. Going over the input backwards cancels out the backwards copying (that -= 1 thing).