here's a quick introduction to counting
sort let's say as an example we are
trying to sort this array into an
ascending order and counting so it works
the best when the range of numbers each
value could have is very small in the
array so let's say the range of values
that we could have for each item is 0 1
2 & 3 the first part of applying
counting sort is going to be finding the
starting index for each number and it's
going to be clear what I mean by that in
a second and the first step for doing
that is going to be counting the number
of occurrences for each number in the
array so for this example there's only
one occurrence of 0 and 3 occurrences of
1 so I'm going to write down 1 and 3 and
then 2 occurrences of 3 and 0 currencies
of 2 and we can store these numbers in
an array of length 4 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
accumulatively
what I mean by that is the first number
at index 0 stays the same and the second
number will be 1 plus 3 equals 4 and the
third number will be 4 plus 0 which is
equal to 4 and the fourth number at the
index 3 will be 4 plus 2 which is equal
to 6 after that step we have the numbers
1 4 4 6 4 the numbers 0 1 2 & 3 the next
step is going to be shifting this whole
array to the right by one cell and we're
going to do that by looking at this
array from right to left we're going to
first start with the last index which is
in x3 in this particular case and the
value there should be the value that's
currently in index 2 so we're going to
put four in x3 and we're going to do the
same thing for in x2 the value here
should be what's in index one currently
so it should also be 4
and at index one we're going to put one
at index zero we're going to put zero
and these numbers 0 1 4 4 are actually
the starting indexes for the range of
numbers we have in this particular case
0 1 2 & 3 and here's one way to think
about it
if you look at the number 3 or the index
3 the corresponding number the
corresponding starting index is 4 and
that's because when we sort this array
the number 3 will start at the index for
another way to think about it is that
there are 4 items that should appear
before the number 3 in the sorted array
and that should be obvious if you just
look at the first array that we
constructed there's one occurrence of 0
3 occurrences of 1 and 0 occurrences of
2 so adding them up there are 4 items
that should appear before the number 3
and that's why the starting index for
the number 3 is 4 once we have the
starting index for each number the rest
is relatively easy we're going to first
initialize a new array that's the same
length as the original rate so length 6
in this particular case and then we're
going to iterate it through the original
array 1 by 1 when we are looking at the
first element of this array which is 1
we're going to check what distorting
index should be for this number from the
array that we constructed we see that
the starting index is 1 so we're going
to put this number into index 1 of the
new array and then we're going to
increment our starting index by 1 and it
becomes 2 and this is so that when we
look at the second instance of the
number one will know that it should
going to the index 2 instead of 1 and
then we're going to increment it again
we'll do the same thing for each number
of this array from left to right until
we get to the last number in the
original array
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 sorted array is
exactly the same as the order in which
they appear in the original array this
wouldn't matter if there were just
number one but if they represented
underlying meanings to them for example
if there were ages of people three
different people let's say Emily Tom and
George then we might care if they appear
in the same order or in a different
order in this sorted array as the
original unsorted array now let's
quickly go through a few important
properties of counting sort first of all
as I mentioned it's a stable sorting
algorithm and the time complexity for
this algorithm is Big O of M plus K
where n is the number of items that we
have in the original array and K is the
range of numbers that we could have for
each item in the array and finally the
auxiliary space complexity is Big O and
plus K for counting sort because we need
to create an entirely new array with
blanks and the same size as the original
array as well as an array of length K to
keep track of the starting index for
each number