Xinok Sort (was: Sorting algorithm)

[Xinok]

On 10/8/2011 11: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

And to follow up on this post, I created a permanent page for xinok sort 
on Sourceforge. There's nothing new to see on this page yet, but I'll 
work on that in due time.

https://sourceforge.net/projects/xinoksort/

My first goal is to write an implementation which I can contribute as 
the new stable sorting algorithm for Phobos. This includes string 
mixins, ranges, asserts, unittests, and anything else that is required. 
If anybody wants to assist me with this, I welcome the help.