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

Am Wed, Apr 19, 2023 at 09:27:14PM +0200 schrieb Hans Petter Selasky:
> > > qsort() is frequently used to do all kinds of sorting, and some pointed out that qsort() can technically be any kind of sorting algorithm, but looking around it is not.
> > 
> > Because there are variants that are guaranteed n log n? Which is better
> > than your n log^2 n.
> 
> Only so-called mergesort() algorithms can do sorting in O(N log N) time,
> from what I know.

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.

Joerg