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
