P is for Practical  
PerlMonks 
Re: An informal introduction to O(N) notationby FoxtrotUniform (Prior) 
on Feb 08, 2003 at 23:26 UTC ( #233791=note: print w/ replies, xml )  Need Help?? 
So is quicksort, in the worst case. :) Mergesort and heapsort are both O(N log N) in the worst case. Most of the time, there's no difference in asymptotic order between the average and worstcase inputs, but every once in a while, something (like quicksort) comes along and bites you on the ass on certain inputs. Quicksort expects its input to be mostly random; ordered input will mess it up. (Think about building a binary tree from ordered input: you'll get a linear list, which is O(N) nodes deep, not a nice bushy tree, which would be O(log N) nodes deep.) Something to think about when building divide and conquer algorithms. 
In Section
Meditations

