Quantum Bogosort

The real reason they're building the QNC

I'm going to assume that you know what bogosort is. If you don't, here's the algorithm:

1. If the list is sorted, stop.
2. If it isn't, shuffle the list randomly.
3. Go back to step 1.

Obviously this is extremely inefficient. However, there's a solution to this inefficiency, and this solution is quantum computing. Because of the many-universes hypothesis in quantum physics, a list that is sorted randomly will create an infinite number of universes, with some universes containing a sorted list. In this case, quantum computing can make bogosort work in O(n). Here's the new algorithm:

1. Shuffle the list randomly.
2. If the list is sorted, stop.
3. If it isn't sorted, destroy the entire universe.

Since the only survivors of this rather apocalyptic approach to computing will be in universes where the list was sorted after the first shuffle, it is quite efficient. Checking if a list is sorted requires n-1 comparisons, and I'm going to assume an entire universe can be destroyed in O(1), as it only ever has to happen once. Thus, bogosort becomes an O(n) sort algorithm.

The Other Tree