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.
I think Phobos would benefit most from a good implementation of
Timsort, perhaps enough to even ditch the unstable sort which
I've found has some bad test cases (try sorting
swapRanges(arr[0..$/2], arr[$/2..$])). My algorithm is very
similar to Timsort, but Timsort is more highly tuned, so it
would probably beat my algorithm in most cases. In a few
benchmarks I've seen, Timsort even beats quicksort.
The only downside is that Timsort may require up to O(n/2)
additional space, and if it fails to allocate enough memory, it
simply fails to sort the list. That's the benefit of my
algorithm, it allocates O(n/1024) additional space by default
and can reduce it further if needed. However, the "range swap"
that my algorithm uses could easily be added to Timsort as
well, so we could have the best of both worlds: The speed of
Timsort with the low memory requirement of my algorithm.
This is my proposal: Replace the stable (and unstable?) sort in
Phobos with Timsort, including the additional range swap step.
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.
