Optimizing Inefficiency: the quest for the worst sorting algorithm
medium.freecodecamp.org
medium.freecodecamp.org
for (int i = 0; i < in.length; i++) {
Thread t = new Thread(new Runnable() {
public void run() {
Thread.sleep(in[i]);
out.append(in[i]);
}
}
t.start();
}Gravity effectively gives infinite free "threads" for the falling and it engages in accounting tricks with assumptions - normally the starting state set up is taken for granted because either it is already there or would always have to be done the same way (no getting around reading in the N numbers) which is more involved in a physical system.
I liken it to being asked to give the value of pi and giving the answer as a red circle split by a green line in the center and writing length of red divided by the length of green. Technically correct and efficient in calculations but extracting it involves more work not in the solution.
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.