Now the next step is called computing cumulates,

and that's a really easy thing as well.

All we do is we go through the count array, and simply,

at each step, we add the current one to the sum computed so far.

So if we look before, we had two a's and three b's.

So that means that there's five letters less than c, that's the a's and the b's.

And there's six letters less than b, and eight letters less than e, and so forth.

And that's just obtained by, we start with 2, add a 3 to it,

get 5, add 1 to it to get 6.

And with that one pass through the count array, then we can find out,

for example, there's six keys less than b, and eight keys less than e.

And those cumulates tell us where the d's go in the output.

There's 6 keys less than d, and 8 keys less than e,

so the d's have to go in a[6] and a[7].

So this is an array of indices that is going to tell us how to

distribute the keys in the output.

So that's the next step, access the cumulates,

using the key as index to move items.

So let's take a look at,

so now remember when we see an a, we're just going to count that as 0.

So we're going to go to count[0], and that will access this entry in the count array.

So we go through the whole array to be sorted, and we move each key

exactly to where it has to go, and we'll do that one at a time now.

So when i is 0, we're looking at the d.

The count array corresponding to d has 6, so it says,

just put d in there, and increment that.

That means if you have another d, it's going to go into 7.

And these things,

the way we precomputed them are not going to run into one another.

So now a, now that goes in 0, and

we increment the count array corresponding to a.

Next thing is c, and so that says to put it in 5,

and then increment the count array corresponding to c.

And f, let's put it in 9.

Next is b, we put it in 2, sorry, another f, we put in 10.

Next is b, that we put in 2.

So you can see, the keys from the input are getting distributed in the output

according to the counts and the cumulates that we've pre-computed.

So now we get the other d, which goes into 7.

We get another b, which goes into 3, and

an increment of 4 to move where the next one goes.

f goes into 11, the last b goes into 4,

the e goes into 8, and the second a goes into 1.