My favourite sorting algorithm is multiverse sort, which runs on O(n): First, check if the list is sorted. If not, destroy the universe.