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