[WJW]

Checking if a list is sorted is O(N) if you do it in a single thread since you'd have to check all the elements. If you can do it with a prefix sum or something, it should be possible to do it in O(log N) over many cores.

Btw, the quantum bogosort also assumes that destroying the universe is O(1), which seems unlikely. Clearly, when sorting a bigger list there is more information in the universe (ie the list). Since information and energy seem to have some equivalence in quantum dynamics, is does not seem unreasonable that destroying a universe with more information in it would take longer and so destroying the universe cannot be O(1).

[michaelmior]

> Clearly, when sorting a bigger list there is more information in the universe (ie the list).

I don't think this is necessarily true. You could argue that the list is simply a bigger fraction of the information in the universe.

[bmm6o]

Does it matter how long destroying the universe takes, since that's in the unsorted branch? The universe with the sorted list continues immediately, the cleanup is handled elsewhere.

[WJW]

I suppose it would depend on if your multiverse has stop-the-world GC or can do it concurrently.

[bmm6o]

The GC pauses clocks, too. There's no way to detect a pause from inside the universe.