12/29/2012 10:49 PM, ixid пишет:
On Monday, 7 November 2011 at 20:33:19 UTC, Xinok wrote:
Recently, I've been working on my sorting algorithm, doing what I can
before I implemented it into std.algorithm. Recently, I've found
myself referring to Timsort for ways to optimize my algorithm, but
that made me think, why not use Timsort instead? It was originally
designed for Python, but it was apparently good enough for Java to
adopt it as well.
[snip]
An explanation of Timsort can be found here:
http://svn.python.org/projects/python/trunk/Objects/listsort.txt
My algorithm can be found here (see the blog for more details):
https://sourceforge.net/projects/xinoksort/
This sounds good, you should also contact the forum user Philippe Sigaud
to see if he's made any progress with his templated sorting network idea
for small number of items and combine the two to provide very effective
sorting.
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.
What's would be truly awesome at the moment is highly efficient
version(s) of sort(s) customized for small ranges. And IRC that's what
Philippe's sorting networks were good at.
--
Dmitry Olshansky
