On 12/18/12 9:21 PM, bearophile wrote:
Andrei Alexandrescu:
A very efficient sort for various small fixed sizes is a great
complement for quicksort.
Do you mean to use it when the input is very short, or when the
QuickSort recursion has produced a very small subarray?
The latter.
In the first
case it's useful, but in the second case I've seen it's more efficient
(maybe not for huge arrays, but it is more efficient for normal arrays
in RAM) to not call a specialized sort for such small sub-arrays, and
instead just stop the QuickSort recursion and produce a locally unsorted
array, and then call an insertion sort on the whole data.
That's a commonly used approach, but I think it can be improved.
Andrei
