"Andrew C. Greenberg" :

(about quicksort)

> 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.

Making random permutations is costly, and *usually* useless. Several real
implementations use just the median discrimination: choose 3 items, e. g.,
first, last, and something in the middle, and use the median one as the
pivot. Then, in the case of already sorted arrays the n*log n complexity
is maintained. Of course, Master, guarantee you will have not, but the
Obscure Side of the Force hasn't too much chance to do any harm. But this
has nothing to do with Smalltalk...


Jerzy Karczmarczuk
Caen, France