Surely O(n) for checking whether it is sorted?

You could just destroy all universes to ensure it's sorted in the remaining reality.

I'm confused. What reality is remaining if all universes are destroyed?

None, but in it the list is sorted.

Or rather a reality wherein it wasn't sorted doesn't exist anymore.

True although not very helpful if you actually want to do something with the sorted list. But I suppose if you cease to exist, so does whatever problem sorting the list was intended to solve.

(the problem of destroying which universe is also left as an exercise to the reader)