[PATCH v2 0/7] Refactor qsort implementation

[Sergey Senozhatsky]

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