(snip on sorting algorithms and implementations)
The recent suggestions for quicksort is, when doing the recursion (as previously noted, using an explicit stack, not recursive calls) not to process very small partitions, but just return. Then, after the quicksort part is finished, do in insertion sort on the whole array.
If elements are close to their final position, insertion sort (with the right choices) is fast, making up for the partition start overhead of quicksort. (The minimum partition size might be about three.)
(Good quicksort doesn't use a fixed array element as the pivot for a partition, but maybe the median of three elemennts. That pretty much avoids the O(N**2) worst case.)
-- glen