Regarding implementing a stable sort for Phobos

[Xinok]

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.