[esrauch]

> 3. The input to a sorting algorithm like abacus sort is a list of numbers. Even if there are n numbers, the number of "beads" you need to simulate is exponentially proportional to the length of the longest single number.

I think this is where we'd mismatch: I'd assume baked into the problem space is that you have N numbers to sort, they are each of size K where K is fixed and bounded. As a solution to "sort these N 16-bit ints, for some arbitrary N". It would be same problem space that can be solved in O(n) with bucket/counting sorts.

[yalue]

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)