I don't agree with that list, but I think quicksort is given way more weight than it deserves. I guess it's a desired result of whomever named it "quicksort".

It's not particularly quick, has horrible worst case guarantees (which, if you care to improve, would make it slower still and very complicated), and is easy to get wrong on many accounts (repeating elements; already sorted input; unlimited recursion depth).

heapsort is simpler than quicksort, and has the best worst-case complexity you can get. It's not stable, but then neither are most quicksorts.

quicksort has its place, but it gets a lot more attention than it deserves.

I agree, but you have to jump all over your data when you do a heapsort, blowing your cache.

It has nice worst-case guarantees, but a well-implemented quicksort has good cache locality.

The main advantage to quicksort is that it's still the fastest average-case-in-practice of the common algorithms. If you want an O(nlogn) worst-case, introsort combines quicksort, which is fast on average but O(n^2) worst-case, with a fall-back to an O(nlogn) heapsort, with a guarantee that it'll never take more than O(nlogn) before it falls back, making it still worst-case no worse than O(nlogn). It'll of course be a constant-factor slower in those fall-back cases than if you had just used heapsort or something directly, but it'll asymptotically be no worse, and on average will get you the nice quicksort win.

Link: http://en.wikipedia.org/wiki/Introsort

> The main advantage to quicksort is that it's still the fastest average-case-in-practice of the common algorithms.

I don't think that's true if you average over the available distribution of _implementations_ in the wide. Almost all implementations do one to three of the "crimes" I mentioned above. And frankly, I've met too much real world cases that triggered an n^2 behaviour on an existing implementation to ever settle for anything with worse than n*log n worst case.

If you're looking for the fastest-in-both-theory-and-practice algorithm, that's TimSort, but it's not in place. The places _in practice_ where Quicksort is the right answer are few and far between. I haven't seen any in the last 10 years.