This I was not expecting:

https://www.reddit.com/r/programming/comments/9v8ouc/an_overview_of_sorting_algorithms_and_a_pretty/e9ajt1o/

On Thursday, 8 November 2018 at 14:36:45 UTC, Atila Neves wrote:
> This I was not expecting:
>
> https://www.reddit.com/r/programming/comments/9v8ouc/an_overview_of_sorting_algorithms_and_a_pretty/e9ajt1o/

Could be the DRuntime and libC calls that are made by `swap`, `move*`, etc. Would need to look at the code and generated asm though.

On Thursday, 8 November 2018 at 14:36:45 UTC, Atila Neves wrote:
> This I was not expecting:
>
> https://www.reddit.com/r/programming/comments/9v8ouc/an_overview_of_sorting_algorithms_and_a_pretty/e9ajt1o/

I wonder if they uses the same algorithm.
I mean: qsort could sound like quicksort but is not specified anywhere.

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

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."

On Thursday, 8 November 2018 at 14:36:45 UTC, Atila Neves wrote:
> This I was not expecting:
>
> https://www.reddit.com/r/programming/comments/9v8ouc/an_overview_of_sorting_algorithms_and_a_pretty/e9ajt1o/

I didn't see a build line. Assuming LDC, one thing that can happen is that code from druntime/phobos may not be optimized as well as code passed in on the build line (ie. manual.d) unless LTO against druntime and phobos is used. Using LTO to include druntime/phobos can be done by including:

   -flto=<thin|full> -defaultlib=druntime-ldc-lto,phobos2-ldc-lto

on the build line. (Personally I'd start with 'thin' LTO and switch to 'full' only if there's an issue.)

Using LTO on only D could result in a comparison inequity. However, it is legitimate for comparing std.algorithm.sort to manual.d.

--Jon

On Friday, 9 November 2018 at 00:31:32 UTC, Jon Degenhardt wrote:
> On Thursday, 8 November 2018 at 14:36:45 UTC, Atila Neves wrote:
>> This I was not expecting:
>>
>> https://www.reddit.com/r/programming/comments/9v8ouc/an_overview_of_sorting_algorithms_and_a_pretty/e9ajt1o/
>
> Using LTO on only D could result in a comparison inequity. However, it is legitimate for comparing std.algorithm.sort to manual.d.

I gave LTO a try for this (Mac OS). It did not change anything. Timings I saw were consistent with Atila's report, with and without LTO.

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?

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."

That is indeed what the ddoc says. The code, however:

----------------------
        static if (ss == SwapStrategy.unstable)
            quickSortImpl!(lessFun)(r, r.length);
        else //use Tim Sort for semistable & stable
            TimSortImpl!(lessFun, Range).sort(r, null);
----------------------

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

On Friday, 9 November 2018 at 09:34:10 UTC, Atila Neves wrote:
> On Thursday, 8 November 2018 at 17:43:47 UTC, JN wrote:
> That is indeed what the ddoc says. The code, however:
------------

Check my answer I didn't see yours. It seems a hybrid algorithm, quickSortImpl it's not a pure quick sort implementation actually.

Andrea