Quantum sort

A quantum sort is any sorting algorithm that runs on a quantum computer. Such an algorithm could at best be linearly faster than any existing sort algorithm (if based on comparisons like classical algorithms), but no such algorithm has actually been implemented.

An in-joke among some computer scientists is that quantum computing could be used effectively implement a bogosort; based on the many-worlds interpretation of quantum mechanics, this quantum sorting would consist of permuting the list randomly and using the outcome in the universe where it is correctly sorted. How to determine this universe is not specified, nor are the mechanics of the other operations.

See also

• Quantum algorithm
• Quantum computing

External link

• bogo-sort in the Jargon File (with a discussion of the joke quantum sort)