"An in-joke among some computer scientists is that quantum computing could be used to effectively implement a bogosort with a time complexity of O(n). It uses true quantum randomness to randomly permute the list. By the many-worlds interpretation of quantum physics, the quantum randomization spawns an infinite array of universes and some of these will be such that the single shuffle had produced the list in sorted order because the total number of distinct orderings, though large, is not infinite. The list is then tested for sortedness (requiring n-1 comparisons); should it be out of order, the computer triggers its “destroy universe” operation. Only in the surviving universes will there be observers to see that the randomization worked first time and that the list is in sorted order. Note, however, that even here there is no free lunch — while this algorithm is O(n) in time, permuting the list requires that we consume O(n log n) bits of quantum randomness."

Bogosort - Wikipedia, the free encyclopedia