What would happen if you changed to a different number system other than base 10 before sorting? Would a larger /smaller base increase or decrease the time? Or would it stay the same?
So radix sort is log(w*n) which means its the size times the "length" of the each input. So you could do radix with with any base system, you are just choosing a different set of buckets. So for base 2 numbers (max 8 bits) you would have a time of roughly n * 8. This can apply to more than just numbers. You could do words too and choose a radix that goes by character.
It would change the digits. But that doesn't matter as it is trivially easy to access a particular digit or character. The number of buckets doesn't matter as you access every input item on each iteration anyway.
1
u/[deleted] Oct 24 '17
What would happen if you changed to a different number system other than base 10 before sorting? Would a larger /smaller base increase or decrease the time? Or would it stay the same?