Re: git: 8dcf3a82c54c - main - libc: Implement bsort(3) a bitonic type of sorting algorithm.]

On 4/20/23 11:20, Joerg Sonnenberger wrote:
> Am Wed, Apr 19, 2023 at 11:47:35PM +0200 schrieb Hans Petter Selasky:
>> On 4/19/23 23:17, Joerg Sonnenberger wrote:
>>> That's false. The difficult part of QuickSort is the median selection.
>>> This can be done in O(n) using the median of median algorithm and when
>>> combined into the main algorithm, much of the work for the median
>>> selection also helps the partition step.
>>
>> Hi Joerg,
>>
>>  From what I know, they all fall back to other sorting algorithms using
>> malloc(), in the end.
> 
> Please, just go and read:
>    Blum, Floy, Pratt, Rivest, Tarjan: Time Bounds for Selection, 1973.
>    [https://people.csail.mit.edu/rivest/pubs/BFPRT73.pdf]
> 
> If you want a slightly more variant:
>    Alexandrescu: Fast Deterministic Selection, 2017.
>    [http://erdani.org/research/sea2017.pdf]
> 
> Short answer: QuickSort requires O(log N) extra space, which is
> essentially a fixed cost given the natural address space limitations.
> Unless operating in a seriously confined environment, that's a perfectly
> fine use of the regular stack.

Hi Joerg,

Thanks for the references you've provided. After reading through the 
paper from 1973, I have the impressions it is about solving the 
so-called pivot selection problem.

The basic QuickSort idea was introduced in 1961, according to the paper 
you referred to:

C. A. R. HOaRE, Find (Algorithm 65), Communications of the ACM, July 
1961, pp. 321-32

The other paper you refer to:
http://erdani.org/research/sea2017.pdf

is about different ways to implement QuickSort and how to mitigate 
problems about pivot selection and performance.

Looking around, qsort() in libc's around the globe is so-to-speak 
equivalent to variants of QuickSort:

Example 1: Android

https://android.googlesource.com/platform/bionic/+/754c178ae551aedcbbfd3bfd1c1c3b710d9ad989/libc/stdlib/qsort.c

Example 2: Linux (GLibc)

https://github.com/lattera/glibc/blob/master/stdlib/qsort.c

Example 3: NetBSD

http://cvsweb.netbsd.org/bsdweb.cgi/src/lib/libc/stdlib/qsort.c?rev=1.23&content-type=text/x-cvsweb-markup

Example 4: Darwin

https://github.com/apple/darwin-xnu/blob/main/bsd/kern/qsort.c

And FreeBSD of course.

Why not allow for more sorting competition inside FreeBSD?

If libc is not the place, maybe an own library, like libsort is more 
appropriate?

Would that be any better if bsort(3) was in its own library, and 
developed from that?

--HPS