# 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:

- If the list is sorted, stop.
- If it isn't, shuffle the list randomly.
- 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:

- Shuffle the list randomly.
- If the list is sorted, stop.
- 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