Timsort vs some others

[Andrei Alexandrescu]

On 12/18/12 5:50 AM, Peter Alexander wrote:
> On Tuesday, 18 December 2012 at 06:52:27 UTC, Xinok wrote:
>> On another note, I highly doubt that std::sort uses a "median of
>> medians" algorithm, which would add much overhead and essentially
>> double the number of comparisons required with little to no benefit.
>> More likely, it simply chooses the pivot from a median of three.
>
> Different implementations use different strategies.
>
> libstdc++ seems to use median of 3.
>
> The Dinkumware standard library (which ships with MSVC) uses median of 9.

We should use a deferred pivot algorithm that I thought of a long time 
ago but never got around to test.

One thing about current pivot selection approaches is that they decide 
on a strategy (middle, median of 3, median of 9, random etc) _before_ 
ever looking at the data.

A different approach would be to take a look at a bit of data and _then_ 
decide what the pivot is.

Consider the following approach:

size_t partition(T[] d)
{
     assert(a.length);
     size_t a = 0, z = arr.length - 1;
     auto maxa = a, minz = z;

     for (; a < z && mina <= maxz;)
     {
         if (d[a] > d[z])
         {
             swap(d[a], d[z]);
         }
         if (d[maxa] < d[++a]) maxa = a;
         if (d[minz] > d[--z]) minz = z;
     }
     --a;
     ++z;

/* Here data is already partitioned wrt d[a] or d[z]. If enough progress 
has been made (i.e. a is large enough compared to d.length), choose one 
of these as the pivot and only partition d[a .. z + 1]. Otherwise, use a 
classic pivot choice criterion.
*/
     ...
}

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!


Andrei