And then what you have in the following two for

loops is just the familiar code for the recomputation phase of the counting sort.

We count the number of occurrences of each of the characters in the string and

then we also compute the partial sums of that array.

And then in the end, we go from the right to left in our string S.

We look at the character and we know that the partial sums array contains

the position after the position where this character should be in the order.

So we decrease the counter by one and we save our character

position in the corresponding cell of the array order and

in the end we just return the order of the character.

So this is just an implementation of the counting sort

as applied to characters of string has.

And it works in time proportional to length of the stream

plus size of the alphabet.

because we know that this is the running time of the counting sort for length of

S items, each of which can take only size of the alphabet, different values.

And I need to note here that typically the size of the alphabet is small like for

example, four letters, four streams in a genome, or 26 characters.

If we are only working with the English words, or maybe alphanumeric characters.

Then there will be 26 small letters, 26 big letters, and 10 digits.

But sometimes the alphabet can be very very big, such as Unicode.

And in this case counting sort might not be appropriate.

If your string for example has only 1000 characters but

those are all unique code, and the alphabet size is a few million character,

then maybe you could sort the characters of this string in a more efficient way.