On 18/12/10 4:46 PM, BCS wrote:
Hello Craig,
It was brought to my attention that the quick sort has a very bad
worst case, so I implemented a simple fix for it. Now the worst case
(completely ordered) is the best case, and it only slows down the
general case by a small percentage. I thought to myself, "it can't be
this easy to fix quick sort". Does anyone see a flaw in this simple
fix? Performs much better than Phobos in completely random and
completely sorted data. Perhaps there is another case where it
doesn't do as well?
I think I've seen it stated as: If you know the implementation, you can
always generate a pathological case for QSort.
That's not true for a randomized pivot point (unless you also happen to
know the PRNG... and seed).
