The recursive calls in quick sort are generally expensive on most architectures - the overhead of any procedure call is significant and reasonable improvements can be obtained with equivalent iterative algorithms.

Two things can be done to eke a little more performance out of your processor when sorting:

1. Quick sort - in its usual recursive form - has a reasonably high constant factor relative to a simpler sort such as insertion sort. Thus, when the partitions become small (n < ~10), a switch to insertion sort for the small partition will usually show a measurable speed-up. (The point at which it becomes effective to switch to the insertion sort is extremely sensitive to architectural features and needs to be determined for any target processor: although a value of ~10 is a reasonable guess!)
2. Write the whole algorithm in an iterative form. This is left for a tutorial exercise!

Empirical studies show that generally quick sort is considerably faster than heapsort.

The following counts of compare and exchange operations were made for three different sorting algorithms running on the same data:

Thus, when an occasional "blowout" to O(n²) is tolerable, we can expect that, on average, quick sort will provide considerably better performance - especially if one of the modified pivot choice procedures is used.

Most commercial applications would use quicksort for its better average performance: they can tolerate an occasional long run (which just means that a report takes slightly longer to produce on full moon days in leap years) in return for shorter runs most of the time.

However, quick sort should never be used in applications which require a guarantee of response time, unless it is treated as an O(n²) algorithm in calculating the worst-case response time. If you have to assume O(n²) time, then - if n is small, you're better off using insertion sort - which has simpler code and therefore smaller constant factors.

And if n is large, you should obviously be using heap sort, for its guaranteed O(nlog n) time. Life-critical (medical monitoring, life support in aircraft and space craft) and mission-critical (monitoring and control in industrial and research plants handling dangerous materials, control for aircraft, defence, etc) software will generally have a response time as part of the system specifications. In all such systems, it is not acceptable to design based on average performance, you must always allow for the worst case, and thus treat quicksort as O(n²).

So far, our best sorting algorithm has O(nlog n) performance: can we do any better?

In general, the answer is no.

However, if we know something about the items to be sorted, then we may be able to do better.