# Can I make last part of counting sort become to be starting from lowest index?

Counting sort is originally like below code.

for (int i = 0; i <= 5; i++) c[i] = 0;
for (int i = 1; i <= 8; i++) c[a[i]]++;
for (int i = 1; i <= 5; i++) c[i] = c[i] + c[i - 1];
for (int i = 8; i >= 1; i--) {
b[c[a[i]]] = a[i];
c[a[i]]--;
}


In the above, last for loop iterates from last index because of stability of counting sort.

But, I want to iterate from first index 1 as well as maintaining the stability of sorting.

I'm trying and thinking lots of time, I cannot do. How can I do?

• Obviously, your question is valid without any motivation. But, still, why? You have a version of counting sort that works for you, but you want to make an arbitrary-looking change that breaks it, while somehow not breaking it. What's wrong with the original version? – David Richerby Jun 8 '18 at 17:25
• @DavidRicherby I just curious about reverse order, just that. – molamola Jun 9 '18 at 0:11

Prior to the last loop, c[i] holds the index of last element of bucket i plus 1. It's why when you use c[i] to address items in bucket i you need to go back. But c[i-1] contains index of the first element of bucket i, so you can just use it... except that you need index for bucket 0 too.

So the simplest way is to modify third cycle making it to write initial index of bucket i to c[i]. It may be done f.e. with extra temporary (note that i in revised loop starts from 0):

sum = 0;
for (int i = 0; i <= 5; i++)
{
sum += c[i];
c[i] = sum - c[i];
}


Note that since indexes in b starts from 1, you need to pre-increment c[a[i]] in new version of last loop (if indexes in b should go from 0, do post-increment instead):

for (int i = 1; i <= 8; i++)
{
c[a[i]]++;
b[c[a[i]]] = a[i];
}