Bogosort is at best linear, since we have to check if the list is sorted.

Quantum Bogosort guarantees the best performance, since it destroys all universes where the list remains unsorted after the first shuffle.