Quantum sort: O(n) 1. Use quantum device to randomize order of array 2. Check if sorted 3. If not sorted, destroy universe In all universes which are left,

Quantum sort: O(n) 1. Use quantum device to randomize order of array 2. Check if sorted 3. If not sorted, destroy universe In all universes which are left, the array is sorted. (Dependencies: Many worlds interpretation, Doomsday device.) Edit: Formatting.