Re:Proving that Android’s, Java’s and Python’s sorting algor...
by thaumasiotes on Tuesday February 24, 2015 @07:15PM
(#9104478)
OK. But if you have control of the comparison routine, you can easily force mergesort to perform a quadratic number of comparisons by having the comparison function call itself an appropriate number of times. It feels a little unfair to call that a vulnerability in quicksort but not in mergesort.
[ Parent
| on HN ]
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).