Timsort vs some others

[Xinok]

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, 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.

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.