3 ms·
You and barkell are right: I forgot the case of actively malicious input. (other than that worst case cannot practically happen, at least I think, taking a glan
by nadam 14y ago
You and barkell are right:
I forgot the case of actively malicious input. (other than that worst case cannot practically happen, at least I think, taking a glance on this algorithm's pivot selection.)
This could be solved with randomization though. (Onlyy a few lines of code needs to be changed.)
- gjm11 14y agoActually, McIlroy's "killer adversary" will work just fine against typical randomized quicksort implementations! (It effectively constructs the data on the fly, guessing when the sorter is trying to find a pivot.) In that earlier HN discussion there was an extended (and frankly rather fruitless) debate between me and another poster about whether McIlroy's adversary can rightly be said to break randomized quicksort; that was basically terminological, and what is not in question is that if you take a typical randomized-quicksort implementation and feed it McIlroy's evil comparator, you will get order-n^2 performance.