Timsort vs some others

[ixid]

On Wednesday, 19 December 2012 at 02:00:05 UTC, Andrei 
Alexandrescu wrote:
> 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

A while ago in another thread about sorting I believe you 
mentioned the possibility of having templated sorting networks 
for small numbers of items, did that idea come to anything?