here is an introduction to radix sort as
an example let's say we want to sort
this array of six integers each integer
value ranging from 0 through 999 and we
want to sort this array in an ascending
order so that the smallest number comes
first the first step that we need to
take in radix sort is sorting the given
array using counting sort and the keys
that we're going to use for that will be
the last digit in each number so it's as
if using counting sort to store an array
with the values 3 9 0 6 3 & 3 in this
particular case and with that the value
that we have with the smallest key which
is there in this particular case will be
the first element in this sorted array
and after that there will be values with
the second smallest key which is 3 so 50
3 will be the second element and after
that 633 and 233 now we're going to keep
going like that until the very end and
the key thing to remember here is that
counting sort is a stable sorting
algorithm and so the values with the
same keys in this example 53 633 and 233
they appear in exactly the same order in
the storage array as they do in the
original array and it's really important
to use a stable sorting algorithm as a
subroutine for radix sort because if we
use an algorithm that's not stable it
just wouldn't work now the second step
in radix sort is sorting this new array
using counting sort again with the
second last digit in each number as the
key this time once we do that the new
sorted array will look like this and
we're going to repeat the same procedure
with this new array and this time we're
going to use the first digit as the key
and you'll notice that there are some
numbers without any number in that place
so we'll just use 0 as the key for those
numbers once that's done the whole array
is going to be sorted let's now think
about the time complexity of radix sort
first we're going to define some
variable
let's call the number of elements in the
array or the length of the array and and
it's equal to six in this particular
case because we have six elements and
that's called the number of digits that
we need to represent each number D and
we need three digits here and to
represent each number we're using the
base 10 system here and let's call that
B so B is equal to 10 in this particular
case now remember that in each step of
radix sort we sort the array using
counting sort using one of the digits as
the key and the time complexity for
counting sort is Big O of n plus K where
K is the range of keys that we have for
each number and the range of keys in
this particular case is 10 or B because
the key ranges from 0 through 9 and it's
always an integer and so each of these
steps takes Big O and plus B in time and
we need to repeat this procedure three
times in this particular case or D times
in general so the time complexity for
the whole algorithm of radix sort will
be big-oh D times n plus B and this is
quite fast when the range of input is
fairly limited compared to the number of
elements that we have in the array and
in that situation depending on the size
and the nature of the input it can
perform better than an optimal
comparison based sorting algorithm such
as quicksort or merge sort which would
take Big O of n log n in time and one
last thing to note here is that there's
a range of values that we can choose
from for the value of B we chose base 10
just for simplicity and just to show an
example but we could chosen for example
base 100 base 2 for a or any other
positive integer for that matter and
this choice will essentially come down
to making a trade-off between time and
space because the larger value that we
choose for B the more space is required
for the account resource step but at the
same time a larger B or larger base will
imply a smaller D or
less number of digits for each number so
it'll take less time to sort the array
using radix sort as long as B is less
than n