Let's just sells an example.

We're trying to sort this array into ascending order on County still works the best when the range of numbers each valley could have is very small in the rate.

So let's just say the range of values that we could have for each item is there a 12 on three.

The first part of applying county sword is going to be finding the starting index for each number on.

It's gonna be clear what I mean by that in a second on the first step for doing that is gonna be comforting the number of occurrences for each number in the A rate.

So for this example, there's only one occurrence of zero three year occurrences off one.

So I'm gonna write down one and three and then two occurrences of three and zero currencies of two, and we can store these numbers in an array of length.

For in this particular case, once we have these numbers, the number of occurrences for each number, the second step is going to be adding each number to the right of it.

A cumulatively what?

I mean by that is the first number at the next zero stays the same and the second number will be one plus three equals four on the third number will be four plus zero, which is equal to four on the force number.

At the index three will be four plus two, which is a go to six.

After that step, we have the numbers 1446 for the numbers 012 and three.

The next step is going to be shifting this whole array to the right by one cell.

And we're gonna do that by looking at this array from right to left.

We're gonna first start with the last index, which is in next three.

In this particular case on the value, there should be the value that's currently in next to.

So we're gonna put four at the next three.

We're gonna do the same thing for you next to the valley Here.

Should be what's in the next one currently.

So it should also before on at the next one, we're gonna put one at an egg zero.

We're gonna put zero, and these numbers 0144 are actually the starting indexes for the range of numbers we have in this particular case.

012 and three.

And here's one way to think about it.

If you look at the number three or the index three, the corresponding number, the corresponding starting index a sport.

And that's because when we sort this array, the number three will start at the index for another way to think about it is that they're four items that stood up here before the number three in the soda rate.

And that should be obvious.

If you just look at the first array that we constructed.

There's one occurrence off there.

030 cars is a one and zero occurrences of two.

So adding them up there are four items that should appear before the number three, and that's why the starting index for the number three is four.

Once we have the starting in next for each number, the rest is relatively easy.

We're gonna first initialize a new rate that's the same length as the origin are rate.

So length six in this particular case, and then we're gonna iterated through the original array one by one.

When we're looking at the first element of this array which this one we're gonna check what the starting index should be for this number from the array that we constructed.

We see that the starting in excess one.

So we're gonna put this number into the next one of the Nuri and they were gonna increment are starting in next by one on it becomes too.

And this is so that when we look at the second instance off, the number one will know that Ace should going to the inn next two instead of one.

And then we're gonna, in commit it again will do the same thing for each number of this array from left to right until we get to the last number in the original rate.

Now, you might have noticed that this process makes counting sort a stable sorting algorithm.

What that means is that, of course, if you look at different instances of the same value, for example, the number one the order in which they appear in the new sordid array is exactly the same asked the order in which they appear in the original rate.

This wouldn't matter if they were just number one, but if they represented underlying meanings to them.

For example, if there were ages off people, three different people, let's say Emily, Tom on George.

Then we might care if they're appear in the same order or in a different order in this sordid array as the original unsorted array.

Now let's quickly go through a few important properties of county sort, first of all, as a mission.

It's a stable sorting algorithm on the time complexity for this algorithm is ba golf and plus que where n is the number of items that we have in the original.

Ray and Kay is tthe e range of members that we could have for each item in the rain.