Talk:Sorting algorithm: Difference between revisions

Revision as of 21:16, 30 November 2015

Revision as of 21:18, 30 November 2015

Line 642:

:: These are all [[comparison sort]]s, and so cannot perform better than {{math|O(''n'' log ''n'')}} in the average or worst case.

: There are strange scope of quantification issues.

: Saying a sorting algorithm is O(nlogn) allows the execution with particular input to be less than nlogn; bubble sort doingtaking O(n) comparisons is not a surprise; it does not contradict the bound.

: Some algorithms are strictly Θ(nlogn). Heapsort goes through all the motions no matter what. But that doesn't mean all sorting has such a lower bound.

: Saying a sorting algorithm is &Omega(nlogn) says it can never do better than nlogn. Bubblesort does better once in a while.