But thats sort of the point.

I _have_ read about quicksort. Some of these other methods, not so much.

That for me makes this a useful and interesting story.

If you use a randomized implementation the worst-case behaviour is expected to be O(n log n).

(Worst-case in the input, averaged over your random bits.)

While using a randomized pivot implementation decreases the _likelihood_ of encountering a worst case, quicksort's worst-case behavior remains O(n2). See the last pages of

http://www.cs.duke.edu/~reif/courses/alglectures/skiena.lect...

I don't know that I've actually experienced a worst-case quicksort situation but I do know of a particular job using quicksort that ran far, far too long - indeed it never completed the quicksort step, because...

After 6 hours of sorting (all previous runs had completed the sort step in 40 minutes or less) we finally killed it, changed the sort implementation, fired it up again and never had the same problem again. It was an enterprise time-critical job running on a mainframe that simply had to complete within 24 hours of start.

Depends on your definition of worst-case behaviour.