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