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.
