This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [PATCH v2 0/7] Refactor qsort implementation
- From: Sergey Senozhatsky <sergey dot senozhatsky dot work at gmail dot com>
- To: Adhemerval Zanella <adhemerval dot zanella at linaro dot org>
- Cc: libc-alpha at sourceware dot org
- Date: Mon, 3 Sep 2018 17:29:28 +0900
- Subject: Re: [PATCH v2 0/7] Refactor qsort implementation
- References: <20180831204238.10626-1-adhemerval.zanella@linaro.org>
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