Timsort vs some others

[Andrei Alexandrescu]

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