Timsort vs some others

[Peter Alexander]

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.