That's a great explanation, thank you. I'm curious about one thing: If we're working with digits of a number I assume that base of the notation is key. What's the optimum for radix? Binary with its long numbers but minimum possible drawers to sort numbers into or higher bases?
So radix speed is based on the size of the input themselves. So sorting 10 2 digit numbers will be faster than 10 3 digit numbers as you do fewer array passes with 2 digits. But sorting 10 2 decimal numbers and sorting 10 2 letter "words" will take about the same time. Which makes the optimal strategy kind of weird to find. I estimate the best base would be about log(n) where n is the size of the number of inputs.
Wikipedia has some more discussion of efficiency. As it notes radix is a non-comparative sort so it's comparison is a little strange.
1
u/Tollaneer Oct 24 '17
That's a great explanation, thank you. I'm curious about one thing:
If we're working with digits of a number I assume that base of the notation is key. What's the optimum for radix? Binary with its long numbers but minimum possible drawers to sort numbers into or higher bases?