News for hackers. Stuff that matters.
Re:Proving that Android’s, Java’s and Python’s sorting algor... by beagle3 on Wednesday February 25, 2015 @01:39AM (#9105586)
Control comes in many flavors - e.g. you might be able to influence random element selection but not general code flow. (e.g - you might be able to set the seed before the call to quicksort).

And I only mentioned control because that's what McIlroy's example required to use as-is. But as I already stated, it is enough to know in advance the output of the (pseudo) random used to select a pivot to make it go quadratic, which is usually easy -- unless it is cryptographically secure (I've never seen qsort use one. have you?)

So, no, it is completely fair: There is no way to cause mergesort to go quadratic. However, it is quite easy to cause quicksort to go quadratic if you know how it selects it pivots (whether or not you can directly influence it during runtime or not).

There are no comments on this comment yet.