|
|
|
|
|
|
by yalue
2624 days ago
|
|
|
This is true, but note that the problem in general doesn't specify that the ints are only 16-bit. It's already well established that "linear time" sorting algorithms exist (e.g. radix sort) for numbers that are all a bounded size. However, the key is still that the length of each number must be bounded, because that ensures that the length of the input relates to the number of numbers in the list to be sorted, rather than to the length of the largest number. (The Wikipedia article on radix sort gets this right... Just not the one on abacus sort) |
|
|