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/
