here's an introduction to radic 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 radic 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 store to store an array with the values 3 9 0 6 3 and 3 in this particular case and with that the value that we have with the smallest key which is zero in this particular case will be the first element in the sorted array and after that there will be values with the second smallest key which is three so 53 will be the second element and after that 633 and 233 and 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 solid array as they do in the original array and it's really important to use a stable sorting algorithm as a sub routine for radic sord because if we used an algorithm that's not stable it just wouldn't work now the second step in radic sort is shorting this new array using counting short 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 notice that there are some numbers without any number in the place so we'll just use zero 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 radic sort first we're going to Define some variables let's call the number of elements in the array or the length of the array n and it's equal to six in this particular case because we have six elements and let's call the number of digits that we need to represent each number D and we need three digits here 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 radic sort we sort the array using counting sort using one of the digits as the key and the time complexity for counting sord is B 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 to 9 and it's always an integer and so each of these steps takes biger of n 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 radic Sword will be big of D * 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 quick sort or merge sort which will take big go 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 have chosen for example base 100 base 2 4 8 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 counting sord 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 radic sort as long as B is less than n