This is the mail archive of the libc-alpha@sourceware.org mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH v2 0/7] Refactor qsort implementation


On (08/31/18 17:42), Adhemerval Zanella wrote:
> The quicksort have the disvantage of O(n^2) as worse case, however
> current glibc implementation seems to have handle the pivot selection
> in suitable way. Ondřej Bílka has raised questioning regarding it could
> be DoS attack [2], and although I do not dismiss this potentially issue
> (although unlikely due the median pivot selection) I think it would be
> worth to discuss it on another thread along with possible alternatives.

Hi,

So I don't know if there will be another discussion thread, but, just
in case, I ran across Orson Peters' Pattern-defeating quicksort a while
ago
	https://github.com/orlp/pdqsort

A TL;DR description - it's a quicksort which fallbacks to a heap sort
whenever it detects the worst case O(n ^ 2) pattern.

As far as I can tell, the RUST programming language does use pdqsort:
https://github.com/rust-lang/rust/blob/master/src/libcore/slice/sort.rs

	-ss


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]