Should Phobos use Timsort instead? (with a small tweak)

[Xinok]

On Saturday, 29 December 2012 at 19:07:52 UTC, Dmitry Olshansky 
wrote:
> Let me point out that Phobos has got the Timsort for stable 
> sort in 2.061. It's precisely the work of Xinok that was 
> integrated after going through many rounds of review.
>
> It would great to analyze the extra trick that reduces the 
> amount of memory required. If it's proven to be a good 
> speed-size trade-off then it could be integrated.

I suppose it's worth a try. The trick in question takes two large 
runs and reduces them into several smaller runs for merging. The 
problem I foresee is that this may negatively affect the 
galloping mode of Timsort, which is most effective when merging 
two large runs. But I'll add this as a feature to my Timsort 
module anyways and see what effect it has.