::[[Introduction to Algorithms|CLRS]], Theorem 8.1 (3rd ed., p. 193):
:::Any comparison sort algorithm requires {{math|Ω(''n'' log ''n'')}} comparisons in the worst case.
::So thisThis is exactly the bound we're trying to express: no algorithm can havebeat aan worst{{math|''n'' caselog better''n''}} thanlower thatbound in its worst case. The theorem allows linear best cases (it doesn't concern them) and quadratic worst cases (since {{math|''n''<sup>2</sup> {{=}} Ω(''n'' log ''n'')}}). CLRS don't say much about the average case, except giving it as an exercise to proof that linear average case is impossible.
::TheOur current formulation is in fact imprecise. A linear time algorithm still runs in {{math|''O''(''n'' log ''n'')}}, so in that sense it doesn't perform any better. [[User:Qwertyus|Q<small>VVERTYVS</small>]] <small>([[User talk:Qwertyus|hm?]])</small> 21:58, 30 November 2015 (UTC)
