On Tuesday, 13 March 2012 at 14:31:59 UTC, Andrei Alexandrescu
wrote:
On 3/13/12 1:31 AM, Xinok wrote:
- It's a natural merge sort, which is faster on partially
sorted lists,
and adds little overhead for mostly random lists.
- It uses O(log n log n) additional space for merging.
That's 1024 when n is 4 billion. I think you can safely
approximate it with alloca or a fixed-size stack-allocated
array.
How about stack allocated for small lists, and heap allocated for
larger lists? e.g. Limit the stack to 1KiB and use the heap for
anything larger.
- I wrote it to sort random-access ranges *without* slicing,
but I think
the exclusion of slicing makes it slower. I'm writing a
separate
implementation which uses slicing and I'll keep it if it's
much faster.
Having random access implies having slicing.
- To avoid multiple allocations, the user can allocate their
own
temporary memory and pass it to the sort function.
If you need different allocation strategies, I suggest you make
it a policy (like stability is).
- I decided against using pointers. While I could use them to
write
highly optimized code for arrays, pointers can't be used in
safe code
and don't work very well in CTFE at the moment.
Perhaps it's best to have two distinct implementations guarded
by if (__ctfe). The runtime implementation can be @trusted.
If the performance gain is great enough, I'll consider doing that.
Is it worth keeping the implementation *without* slicing? Many
functions
in Phobos do require slicing, including the unstable sort, and
I think
most random-access ranges do or could support slicing.
No need.
I'll leave it out of Phobos.
What would you prefer in terms of memory usage vs performance?
O(n/2)
space is optimal for performance, O(1) (in-place) requires zero
allocations but is slower, and O(log n log n) provides a good
balance.
The latter rounded up to a constant sounds best.
Should I implement concurrency? Merge sort is very easy to
parallelize,
and being in-place or natural doesn't change this fact.
Let's save that for std.parallel_algorithm.
I'll leave it out of Phobos for now.
