Sorting algorithm

[Xinok]

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