From: Michael Campbell <michael_s_campbell@...>
Date: 2003-08-01T04:51:10+09:00
Subject: Re: Feature request: stable sort

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

But then, it's been a few years since I studied the theory of algorithms, so
I might be misremembering.