Quantum sort
Quantum sort is a sort algorithm that runs on a quantum computer. Such an algorithm would be extremely fast, but has not been implemented.
A joke
Quantum sort is also an in-joke among quantum mechanics. It is a theoretical sort algorithm taking advantage of the multiple-universe theory. Although it applies some of the theory and ideas of quantum algorithms, it is purely hypothetical. Nevertheless, it can serve as a vague introduction as to what a quantum algorithm is about.
In essence, one takes a random permutation of a set of elements. According to the many-worlds theory of quantum mechanics, there will then exist a parallel universe in which the set of elements is sorted. According to the theory, one simply destroys all the universes where the set is not sorted, using the principle of quantum immortality to perform useful calculations. Hence, the algorithm has O(n) complexity, which is rare amongst sort algorithms and normally not feasible with just a single pass through the data. In theory, this results in extremely fast performance. In practice this is not exactly possible.
See also
External Links
- bogo-sort in the Jargon File (with a discussion of the joke Quantum sort)