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!

Continue on to Bin and radix sorting

Back to the Table of Contents

© John Morris, 1998