Sorting algorithm

[Xinok]

On 10/7/2011 1:03 PM, Andrei Alexandrescu wrote:
> On 10/7/11 11:42 AM, 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/
>
> This is interesting. What do the numbers in the benchmark represent?
>
> Andrei

I'll just post the code I used for benchmarking. Simply put, smaller 
numbers are faster.

ubyte[16] digest;
uint[] base;
base.length = 1024 * 1024 * 16;
foreach(i, ref v; base) v = i;
randomShuffle(base);

writeln("Is sorted: ", isSorted(base));
writeln("Is length: ", base.length);

SetThreadPriority(GetCurrentThread(), THREAD_PRIORITY_TIME_CRITICAL);
long start, finish;

auto copy = base.dup;
QueryPerformanceCounter(&start);
xinokSort(copy);
QueryPerformanceCounter(&finish);
sum(digest, copy);
writeln("xinokSort: ", finish - start, "\t", digestToString(digest));
assert(isSorted(copy), "Array not sorted");