hey people i would like to suggest an alternate approach to be used for radix sort.
The general approach is to apply counting sort on each digit of every number starting from the units place( now onwards LSB) and going upto the highest place(now onwards MSB)
eg suppose we have the numbers-> 219,357,557,639,426,620,345
so first it applies counting sort on LSB
hence the list will now be
620
345
426
357
557
219
639
then counting sort is applied to the tens plance and so on till MSB
Hence in this case we will have to check for each digits place uptil MSB.
Rather than doing this what we can do is start applying the counting sort from MSB, we will have following cases possible for each place(i.e. thousand, hundred, tens, units etc)
case 1: if all the digits (i.e of different numbers at that place) are different the counting sort will be applied and we will get the sorted list
eg if the numbers are : 128,532,457
then upon applying the modified radix sort we will first apply counting sort on the MSB's, since they are all different we will get the sorted list in one operation only
i.e. we will get 128,457,532
case 2: if 2 or more digits of the same place are equal, in this case we will apply the counting sort(preserving the ordering) and then sort for the next lower place
eg if the numbers are 253,146,223
then upon first applying counting sort we get 146,253,223
then we check for next place and get the result as 146,223,253
so we keep on applying these two cases until we get the sorted list.
Therefore we can easily see that in case of the usual Radix sort, we will have to apply counting sort for each digit place while in case of this modification we can get the sorted list if at some place we get all the digits different ( we can easily use a counter for this)
I would like you people to think about this and tell me in which sorting the complexity will be less always... As far as i think it will be less in the second case.
Thank you
Keywords: Radix Sort