Timsort vs some others

[Andrei Alexandrescu]

On 12/18/12 8:42 PM, Xinok wrote:
> On Tuesday, 18 December 2012 at 15:55:17 UTC, Andrei Alexandrescu wrote:
>> Another approach I wanted to try was to choose the median of K with K
>> increasing with the size of the array. This is because a good pivot is
>> more important for large arrays than for small arrays. As such, a
>> possibility would be to simply sort a stride of the input
>> (std.range.stride is random access and can be sorted right away
>> without any particular implementation effort) and then choose the
>> middle of the stride as the pivot.
>>
>> If anyone has the time and inclination, have at it!
>
> Perhaps a "median of log n" is in order,

Yah I thought so!

> but the trouble is finding an
> algorithm for picking the median from n elements. The so called "median
> of medians" algorithm can choose a pivot within 30-70% of the range of
> the median. Otherwise, there doesn't seem to be any algorithm for
> choosing the absolute median other than, say, an insertion sort.

You don't need to choose a median - just sort the data (thereby making 
progress toward the end goal) and choose the middle element.

> I came up with this clever little guy a while ago which I used in my
> implementation of quick sort: http://dpaste.dzfl.pl/b85e7ad8
> I would love to enhance it to work on a variable number of elements, but
> from what I can comprehend, the result is essentially a partial heap sort.

A very efficient sort for various small fixed sizes is a great 
complement for quicksort.


Andrei