[ilzmastr]

I'm interested in the way you use the word "attack."

I was looking at it from the perspective of you could never run into an input that would consistently sort in O(n^2) using randomized-quicksort.

But your perspective (maybe this article's perspective) is that some malicious adversary could force the sorter to do extra work by knowing in advance the steps that they will take. Am I getting that right? Like from a flops security stand point?

If so, why care about this situation? This only seems like a realistic scenario in very weird domains, like amazon web services messing with everyone's calls to some standard sorting code to charge them more cents for compute time or something...

[alejohausner]

If I'm not mistaken, the attack is aimed at a quicksort implementation where the pivot value is chosen as a median of first, middle, and last values. It would not work on randomized quicksort, of course.

[asdfasdfsd]

Take a look at Denial-of-service attack.