3 ms·
1. It's average-case versus worst-case again. If you implement quicksort recursively in the obvious way, then when you get unlucky it takes order-n stack space
by gjm11 14y ago
1. It's average-case versus worst-case again. If you implement quicksort recursively in the obvious way, then when you get unlucky it takes order-n stack space as well as order-n^2 time.
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 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 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.]
- nadam 14y agoYou 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.