Re: XSort - Sorting algorithms (including Timsort!)

[Xinok]

On Thursday, 12 April 2012 at 05:25:52 UTC, Nathan M. Swan wrote:
On Thursday, 12 April 2012 at 03:04:49 UTC, Xinok wrote:
I just wanted to share this. I started a project a few weeks 
ago on Github to implement several sorting algorithms in D. In 
total, there are 8 modules at the moment, each implementing a 
sorting algorithm or combination thereof.

https://github.com/Xinok/XSort

I just finished Timsort today. It's working, it's stable, but 
I need to spend a little more time better optimizing it.

Cool! To make it a bit more generic, may I suggest making all 
the inputs only have to be "isInputRange", and have it 
converted to an array.

NMS

This incurs different behavior as random-access ranges would be 
sorted in place and input ranges wouldn't be. I could add 
separate functions to make this behavior explicit, but I see 
little point in doing so. It's quite easy to convert an input 
range to an array yourself:

import std.array, std.range;

auto inputRangeToArray(R)(R range)
if(isInputRange!R && !isInfinite!R)
{
        auto app = Appender!(ElementType!(R)[])();
        static if(hasLength!R) app.reserve(range.length);
        app.put(range);
        return app.data;
}