:– [[The Art of Computer Programming|TAOCP]] § 5.3.1 (Sorting and Searching)}}
::A possible replacement is (ref is TAOCP chapter 5): <blockquote>The number of comparisons required by a comparison sorting algorithm is roughly [[Proportionality|proportionate]] to n log n comparisons in the worst case (some algorithms require proportionately n log n comparisons);<ref>{{Harvnb|Knuth|1998|loc=§ 5.3.1}}: The best worst case ... hence roughly n lg n comparisons are needed.</ref> in better cases, comparisonit sortingis canpossible beto performedperform comparison sorting in at most a multiple of n comparisons.<ref>{{Harvnb|Knuth|1998|loc=ch. 5}}: On the other hand, if the keys are known to be randomly distributed with respect to some continuous numerical distribution, we will see that sorting can be accomplished in O(N) steps on the average.</ref></blockquote> -'''''[[User:Esquivalience|<span style="color: #33BBFF; font-family:Lato, monospace'">Esquivalience</span>]]'' <sup>[[User talk:Esquivalience|<span style="color:#00B88A;">t</span>]]</sup>''' 02:05, 6 March 2016 (UTC)
{{Reflist-talk}}
*{{cite book|ref=harv|last1=Knuth|first1=Donald|title=The Art of Computer Programming, Volume 3: Sorting and Searching|date=1998|publisher=Addison-Wesley Professional|edition=2nd}}
