On Sunday, November 18, 2001, at 09:14  PM, Richard A. O'Keefe wrote:

> 	quicksort: begin to: end
> 	    "This is an implementation of the Quick Sort algorithm, which
> 	     is O(n*log(n)), where n is the size of the collection to
> 	     be sorted."
> 	
> The order-of-magnitude claim is FALSE.  Quicksort is O(N**2).
> The worst case does arise in practice.  The #sort[:] methods already
> in ArrayedCollection do not have that problem.

Indeed, and the worst case behavior actually arises in an annying, but 
fairly common, scenario: where the array is already sorted.  Because of 
the low coefficient, Quicksort is beneficial in some cases since it 
behaves like an nlogn sort on average, but it is certainly not best for 
general purpose code where a sorted, or almost-sorted, array is more 
likely to be presented.

Many commercial Quicksort codes impose a random permutation on the array 
before processing, so that the worst case behavior occurs less 
frequently in scenarios where arrays arrive nearly sorted.  Still, this 
doesn't make the code better than it is -- it will still wait 
interminably for some large tables on some occasions.

> SortedCollection is supposed to maintain a collection in order as one
> adds things to it.  I suspect that simply letting it get out of order
> and _lazily_ resorting it using some method that exploits existing
> order (such as natural merge, or perhaps SplaySort) might be better.

Indeed, QS is a nightmare for simple additions to substantially 
pre-sorted arrays.