Each comparison-based sorting algorithm has the worst complexity of . (For big-Omega and similar notations see this Wikipedia page.) For a proof, see these (PPT) or these (PDF) lecture slides or Google for 'sorting algorithm worst case nlogn "decision tree"'.