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");
