News for hackers. Stuff that matters.

A comment on Algorithmic complexity attacks and libc qsort(). Parent comment

Re:Algorithmic complexity attacks and libc qsort() by matslina on Wednesday June 11, 2014 @11:56AM (#7878657)
Mergesort would be a poor choice for qsort() due to the linear space complexity. With N bytes of RAM, you'd only be able to sort (a bit less than) N/2 bytes of data. An in-place algorithm is preferable.

Glibc is the only libc I'm aware of that implements mergesort. It still falls back to quicksort for large inputs though.

[ Parent | on HN ]
Re:Algorithmic complexity attacks and libc qsort() by mzs on Wednesday June 11, 2014 @12:18PM (#7878797)
I just heard about smoothsort: http://code.google.com/p/combsortcs2p-and-other-sorting-algo...

Also, nice little write-up, thanks. I also dig the extracted sort implementations you dug-out: https://github.com/matslina/qsort

[ Parent | on HN ]
Re:Algorithmic complexity attacks and libc qsort() by tedunangst on Wednesday June 11, 2014 @12:51PM (#7878987)
All BSD derived libcs contains mergesort(), and heapsort() as well.
[ Parent | on HN ]
Re:Algorithmic complexity attacks and libc qsort() by mzs on Wednesday June 11, 2014 @01:40PM (#7879283)
True, but parent meant used in the qsort and qsort_r implementations.
[ Parent | on HN ]
Re:Algorithmic complexity attacks and libc qsort() by tedunangst on Wednesday June 11, 2014 @03:31PM (#7879967)
Oh, of course. reading fail.
[ Parent | on HN ]