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

On 4/20/23 00:28, Colin Percival wrote:
> 
> Quicksort with cryptographically randomized pivot selection is O(N^2) worst
> case but O(N log N) average-case-for-worst-case-inputs which is good enough
> for most purposes.
> 
> Quicksort with in-place median-of-medians pivot selection is O(N log N) 
> worst
> case.
> 
> Both of them can be easily implemented with O(log N) extra space (for 
> the call
> stack), and with O(1) extra space if you're insane enough to care.

Yes, I know there are different ways to mitigate O(N^2) behaviour, but 
there is not yet after xxx years of research a way to fully mitigate 
that behaviour.

What I think, there should be some statistics done in our qsort() when 
it goes to O(N^2), and then it could fallback to bsort() for example, to 
avoid issues with malloc().

Or maybe one round of bsort() is enough to make qsort() do its thing 
right. I want to investigate that. Like a hybrid.

--HPS