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

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. They keep track of the sorting cost, and then at 
some point give up, finding a good median. So called radix sorting is 
more appropriate for doing split partition sorting, where you have not 
just +1/0/-1 as return values from the compare() callback function, but 
an actual N-bit indexer. This limits the complexity and recursion.

Sometimes when you know the data to be sorted well, qsort() works great, 
but other times not. And there should be more options in FreeBSD, in my 
opinion.

--HPS