[asdfasdfsd]

That algorithm is only used to create an input pattern. When it is fed back to the same sorting function, it will cause it to go quadratic. If your target is using the same sorting function it will do the same on their side.

This attack is realistic. I have tried it on the glibc qsort, generic quicksort, and Visual Studio qsort, and they were vulnerable.

[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.