Re:The software development final exam: Mathematics
by nadam on Wednesday October 10, 2012 @08:54AM
(#4636076)
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.)
Re:The software development final exam: Mathematics
by gjm11 on Wednesday October 10, 2012 @10:01AM
(#4636341)
Actually, 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.
2. Yup, it recurses, and it looks to me as if it's vulnerable to blowing out the stack in the worst cases. However, it's quite a sophisticated implementation and in practice you're probably only going to see the worst cases if you feed it actively malicious input (see, e.g., http://www.cs.dartmouth.edu/~doug/mdmspe.pdf for a paper about doing this).
[EDITED to add: (1) A little discussion of that paper on HN is at http://news.ycombinator.com/item?id=1723305. (2) I don't know whether McIlroy's "killer adversary" would actually work against this dual-pivot algorithm without some modification; it depends on how well its heuristic for telling when the pivot is being found works against this algorithm. I'd guess that it does work.]