So let’s say I’ve got step 2. figured out with vacuum decay or similar, how do I check if the list is sorted in O(1) to determine if I destroy the universe or not?

And given that the list being sorted is a one in n! chance, often enormously less likely than than hardware malfunction, wouldn’t the algorithm mostly produce malfunctions rather than sorted lists?

(Genuinely curious if I’ve got the right understanding of the CS and potential physics.)

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).

> 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.

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.

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

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

Eh. You have to assess whether the list is sorted before you destroy the universe, thus increasing the total algorithm runtime complexity.

Yeah, sounds like an O(n) sort to me.

In each universe, yes. But if you have m universes...

That operation is also left as an exercise to the reader

A cop out. :)

Won't any quantum "destroy the universe" operation result in one destroyed universe and one that isn't?

As a fall-back (in case the universe-destroying resources are busy), you could also sort the list classically if the quantum randomization didn't do it. There'd still be that one lucky-bastard-universe that gets all the sorting done in O(1)... As a side note though, please never do this. Our simulators would pull the plug really quickly if we deliberately caused state explosions like that.