From: thealmightydaev@... (Dave Dembinski)
Date: 2003-08-12T05:39:46+09:00
Subject: Re: Feature request: stable sort

"Michael Campbell" <michael_s_campbell@yahoo.com> wrote in message news:<LEEEIDNEKIDGNLMOEIJOEEBNCDAA.michael_s_campbell@yahoo.com>...
> > Also, doesn't quicksort have some nasty input cases where it degrades to
> > O(n^2), or am I thinking of something else?
> 
> If I recall correctly, I think if the input is sorted exactly wrong (ie it's
> in descending order and you want ascending) *AND* the pivot is chosen
> particularly badly, it goes to O(n^2).
> 
> Most modern qsort() implementations use a "middle of 3" choice for pivot, so
> even in the "worst case" scenario, it's better than n^2 (albeit probably
> worse than n log n)

Correct.  Also, in cases where the list is "almost sorted" in one
direction or another, quicksort can have a very nasty running time. 
These cases can be alleviated either through manipulation of the
pivot, as you suggested, or by simply randomizing the list before
giving it to quicksort.  Of course, with randomizing, there's always
the (extremely slim) chance that you'll end up with a sorted list (a
la bogosort), but it's an easier hack than changing the quicksort
algorithm.

Dave Dembinski