Data Structures and Algorithms

Quick Sort  the last drop of performance

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:

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 speedup.
(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!)

Write the whole algorithm in an iterative form.
This is left for a tutorial exercise!
© John Morris, 1998