Quicksort is broken. Is it worth fixing?

the bigger news here is that people are still using angelfire. i half expected that the ads on top were from linkexchange.

It's curious the OP doesn't mention introsort (http://en.wikipedia.org/wiki/Introsort). AFAIK most standard libraries use introsort instead of quicksort.

Introsort uses heapsort when the recursion is too deep and insertsort when the entry is too small.

A really nice essay about Quicksort and it's quirks and border cases. Worth a read!

On the other hand, when developing an application, you should think twice if you really need to write your own sorting routine. Better stick with the system library unless you have some use case that really requires your own sorting implementation.

It is possible to find the median in linear time (quickselect). Pivoting on the median makes quicksort optimal (O(n log(n))) while only using constant space. This is rarely used in practice because the overhead is large compared to the probability of being given a worst-case problem.

http://stackoverflow.com/questions/2105737/has-anyone-seen-t... Another nice discussion on how to deal with the duplicate problem.

There is an algorithm for calculating median in O(n). I was wondering if choosing a pivot that is always a median would speed up quicksort. In theory it should always give O(n log n) time, as recursive calls would always take a half of input array.

Variations of mergesort are starting to have overall higher throughput, while having better worst case complexity.

Timsort is a good example, used in Python and JDK 7.