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

On 4/19/23 14:41, Hans Petter Selasky wrote:
> On 4/19/23 22:17, Jessica Clarke wrote:
>> pdqsort is n log n time, in-place and doesn’t allocate, and is used,
>> for example, for Rust’s standard sort_unstable.
> 
> Like many many people have tried over the years, to improve the belated 
> QuickSort (*) algorithm since it was invented, by catching bad behaviour and 
> then fallback to other algorithms, pdqsort() is not a solution!
> 
> Yes, it is probably "N log N" time, but if you read the code carefully, it 
> falls back to heapsort(), which indeed uses malloc(), which is exactly my 
> point, that I want to avoid.
> 
> Please come forward with a "N log N" time algorithm which is malloc() and 
> alloca() free, and then we'll talk!

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.

-- 
Colin Percival
FreeBSD Deputy Release Engineer & EC2 platform maintainer
Founder, Tarsnap | www.tarsnap.com | Online backups for the truly paranoid