| I was going to comment on this already, but even that's way too "fast" based on the accepted notion of time complexity in theoretical CS... abacus sort should technically be an exponential-time algorithm! (And yes, I disagree with the wikipedia article on this topic, which lists several "possible" time complexities, all of which I consider incorrect.) The reason being that the accepted definition of time complexity in formal literature is standardized not based on the number of "things" in the input (numbers in a list, nodes in a graph, etc.), but on the length of the input string. This is a common pitfall when people reason about time complexity. Here's why this applies to abacus sort: 1. Abacus sort contains integers in its input string--and based on the conventions of formal time complexity, these can not be encoded in unary (if unary encodings were allowed, then several famous NP-Complete algorithms, e.g. bin packing, would have polynomial time solutions based on the length of their input) 2. The value of an integer is exponentially related to its length. For example, making a binary integer only one bit longer can double its value, making it two bits longer will quadruple its value, etc. 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. 4. Even if you think that the number of beads can be simulated with an infinite number of threads, or something, you'd still need to decode the (at least) binary input to a unary number of beads, which will take an exponentially-related amount of memory. Of course, all this is not to say the algorithm isn't cool in practice, for numbers in ranges that reasonable people care about. It's similar to a weakly-NP-complete problem (https://en.wikipedia.org/wiki/Weak_NP-completeness) like integer bin packing, where the time complexity is dependent on the longest number and therefore technically exponential, but in practice solved for any reasonable ranges of values in polynomial time. Edit: By the way, this is why the naive prime-number-checking algorithm (check divisibility of a value v by all values up to sqrt(v) is not an efficient algorithm even though many people incorrectly think it's O(sqrt(n))! It technically takes exponential time relative to the length of bits in the number, so it's basically useless for guaranteeing primality of something like a 4096-bit 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.