Comment by TeMPOraL
15 years ago
Worst case O(\inf), it's known as 'random sort' or 'bogosort'.
Funny thing, it can theoretically be O(1) on quantum computers, assuming the multiple-universe interpretation of quantum mechanics: http://en.wikipedia.org/wiki/Bogosort#Quantum_bogosort ;).
My favorite presentation (http://c2.com/cgi/wiki?QuantumBogoSort) goes approximately like this:
1. Randomize the list. 2. If the list is not sorted, destroy the universe.
Is randomizing a list of n entities once is an O(n) operation. not sure how it would be done in O(1) on quantum computers.
The link that Dove gave suggests there's an idea of quantum randomization that will split our universe into n! universes in constant time.