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
