Sorting algorithm

[Andrei Alexandrescu]

On 10/8/11 10:11 AM, Xinok wrote:
> On 10/7/2011 12:42 PM, Xinok wrote:
>> Hi, it's been years since I've posted here. I just wanted to share
>> something I worked on, a new sorting algorithm. It's a variant of merge
>> sort, but much more memory efficient with only a small loss in
>> performance. The most similar algorithm I know of is Timsort.
>>
>> I had need for a stable sorting algorithm, but the performance of stable
>> sort in Phobos is terrible. This pretty much left merge sort, which has
>> good performance but requires O(n) space. That persuaded me to design my
>> own sorting algorithm.
>>
>> Here, you can find the code, details of the algorithm, and benchmarks
>> (introSort is the unstable sort in Phobos).
>> http://www.neowin.net/forum/blog/422/entry-3737-sort-algorithm-complete/
>
> To follow up on my original post, I wrote a text file which explains the
> algorithm in detail. The most important thing to understand is the
> "range swap", which I tried to explain as simply as possible.
>
> http://cl.ly/0H193k2s0G2T1A002v3I/xinokSort.txt

Nice writeup, but I found it quite difficult to get into. What would 
help is anchoring it with already known stuff (if it's not, the reader 
must assume it's unrelated, which makes things difficult). So it would 
be great if you compared and contrasted range swap with the in-place 
merge algorithm (e.g. http://www.sgi.com/tech/stl/inplace_merge.html), 
STL's stable sort (http://www.sgi.com/tech/stl/stable_sort.html) which 
is O(N log(N) log(N)), and possibly with std.algorithm.bringToFront.

Simply presenting a stylized implementation of swap range would be helpful.

Also there are a few oddities in the text:

* "- Constant additional memory (one memory allocation per thread)" -> 
the parenthesis does not sustain the point. There could be one memory 
allocation but it might allocate a non-constant amount.

* All discussion about tail call optimization is unneeded. Tail calls 
can be converted trivially to loops, so don't mention anything. Feel 
free to convert to loops if needed.


Andrei