The problem with the D GC [OT: Quicksort]

[Frits van Bommel]

Miles wrote:
> I should also mention that this is considered a serious security issue,
> on the same class of the QuickSort algorithm.
> 
> For those not aware of secure programming practices: using QuickSort to
> sort data input by a remote user is considered a bad programming
> practice, because although QuickSort is O(n*log(n)) on average, there is
> a set of input data that makes the algorithm O(n^2). Knowing the
> implementation, an attacker may feed the application with carefully
> crafted data that exploits this weakness.

Of course, if you're only concerned about malicious users sending 
worst-case data (and not about worst-case data appearing randomly) 
there's an easy fix: randomize the data in O(n) :).
Don't laugh, they taught me that in school. And it works, Quicksort will 
remain O(n*log(n)) on average with that simple step performed 
beforehand, no matter the input data.
You'll need to trust your randomizer though, if the attacker can 
influence *that* you're just screwed and should use introsort or merge 
sort or something else with guaranteed O(n*log(n)) behavior if that's 
really what you want...