[musl] Re:Re: [musl] qsort

["David Wang" <00107082@163.com>]

At 2023-02-17 00:07:35, "Rich Felker" <dalias@libc.org> wrote:
>On Thu, Feb 16, 2023 at 11:15:24PM +0800, David Wang wrote:

>> Strange thing is, I made a textbook implementation of heapsort as in
>> following patch, optimized for size 8, the runtime and comparison
>> improved a lot.
>
>Do you have a good theoretical reason why that might be the case?

Smoothsort is way too complicated for me to make out a clear analyze, according to my reading, smoothsort would make the binary tree quite skewed, make the const factor in O(nlogn) bigger for average performance.
Its advantage  is for best case performance when the input is almost sorted.
Following quote  is from the smoothsort paper "Smoothsort, an alternative for sorting in situ",  written by Esger W. Dijkstra 
"""
While heapsort prunes the tree leaf by leaf, smoothsort prunes the tree at the root, and
immediately one of heapsort's charms is lost: while the tree in heapsort remains beautifully
balanced, the tree in smoothsort can get very skew indeed. So why bother about smoothsort at all?
Well, I wanted to design a sorting algorithm of order N in the best case, of order N⋅log N in
the worst case, and with a smooth transition between the two (hence its name).
"""
I think it is safe to conclude:
1. heapsort is better than smoothsort for average performance
2. smoothsort is better than heapsort and  many other sorting algorithm for best case


>
>Yes, I think optimizing out the external memcpy calls for small sizes
>is a good idea regardless of whatever else we do. The code you tested
>is not valid (it has UB via aliasing violations) but we could fix it
>either using __may_alias__ types conditioned on __GNUC__, or exposing
>memcpy intrinsics where they don't result in circular definitions with
>some magic in src/include/string.h. I'd like to do the latter at some
>point anyway.
>

Thanks for pointing this out, I am so not experienced with engineering details, yet.



David