std.algorithm.sort slower than C++'s std::sort for integer arrays

Andrea Fontana nospam at example.com
Fri Nov 9 09:36:09 UTC 2018


On Friday, 9 November 2018 at 07:57:57 UTC, Andrea Fontana wrote:
> On Thursday, 8 November 2018 at 17:43:47 UTC, JN wrote:
>> On Thursday, 8 November 2018 at 15:28:25 UTC, Andrea Fontana 
>> wrote:
>>> I've already said in the past that we probably can improve 
>>> sort() function tuning it for some cases (f.e. short int or 
>>> bytes...). Many languages use some hybrid algorithms like 
>>> timsort & similar. I don't know what D do on phobos...
>>>
>>> Did you consider this?
>>>
>>> Andrea
>>
>> https://dlang.org/phobos/std_algorithm_sorting.html#sort
>>
>> "Algorithms
>> Introsort is used for unstable sorting and Timsort is used for 
>> stable sorting."
>
> Right, what about the others language tested?

Wikipedia:
"Introsort or introspective sort is a hybrid sorting algorithm 
that provides both fast average performance and (asymptotically) 
optimal worst-case performance. It begins with quicksort and 
switches to heapsort when the recursion depth exceeds a level 
based on (the logarithm of) the number of elements being sorted."

Fast analysis follows.

Here it seems qs is used:
https://github.com/dlang/phobos/blob/b16687357013eaa952decdc3d1d03d442b9429cd/std/algorithm/sorting.d#L1857

https://github.com/dlang/phobos/blob/b16687357013eaa952decdc3d1d03d442b9429cd/std/algorithm/sorting.d#L1869

But here it seems it is a hybrid algorithm (not using logarithm):
https://github.com/dlang/phobos/blob/b16687357013eaa952decdc3d1d03d442b9429cd/std/algorithm/sorting.d#L2059

Calling this in some cases (it doesn't sound like heapsort):
https://github.com/dlang/phobos/blob/b16687357013eaa952decdc3d1d03d442b9429cd/std/algorithm/sorting.d#L1622

So I'm not sure documentation is correct.

Andrea









More information about the Digitalmars-d mailing list