3 ms·

I am not an expert of this, but: 1. I think the stack usage of Quicksort is O(log(n)). Which means it is impossible to blow up the stack unless your dataset is

by nadam 14y ago

I am not an expert of this, but: 1. I think the stack usage of Quicksort is O(log(n)). Which means it is impossible to blow up the stack unless your dataset is bigger than the number of atoms in the universe (but in that case how are you keeping it in memory?) 2. For example in Java when you call Arrays.sort() this is called: http://cr.openjdk.java.net/~alanb/6905046/webrev/src/share/classes/java/util/DualPivotQuicksort.java.html http://cr.openjdk.java.net/~alanb/6905046/webrev/src/share/c... (It apparently uses recursion) I know quicksort, but not on this level: these guys researched lots of different quicksort implementations and optmized the hell out of it. This implmenetation is way longer to begin with than my naive quicksort implementation would be and is called 'dual pivot quicksort', which I did not hear about until now, despite I know how the traditional quicksort works.

barrkel 14y ago
Worst case is O(n). Think about it; recursing on one half after finding a pivot which turns out to be the smallest or largest (presuming you recurse on both halves). A malicious attacker may even craft data that causes this behaviour, if they know the library / variant being used.
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 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 ago
    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.
alexkus 14y ago
This is my point, the worst case of stack usage of the basic quick sort algorithm is O(n), not O(log n); O(log n) is the average case. Consider a quicksort algorithm that takes the first element in each partition and uses that as the pivot. When given sorted data it will iterate as: Notation: (left set) _pivot_ (right set) Input: 1 2 3 4 5 () _1_ (2 3 4 5) 1 is chosen as pivot, all elements in right set 1 () _2_ (3 4 5) 2 is chosen as pivot... 1 2 () _3_ (4 5) 1 2 3 () _4_ (5) Note that for each recursion we're construction the input with the aim of leaving one of the partitions empty, so that we only ever sort 1 element (the pivot) each iteration. So that's n-1 levels of recursion with n elements -> O(n) Even if you take the 'middle' (left-middle if even number) element as the pivot it's possible to construct a patalogical case:- Input: 4 2 1 3 5 () _1_ (4 2 3 5) 2 is next pivot for right partition 1 () _2_ (4 3 5) 3 is next pivot for right partition 1 2 () _3_ (4 5) 4 is next pivot as left of middle for even number of elements 1 2 3 () _4_ (5) ... Again, n-1 levels of recursion with n elements -> O(n) On the other point; I'm not saying that every implementation of quicksort out there is susceptible. I'm saying that there are quite a few implementations that are in common use that are just the basic quick sort algorithm and can be made to blow through available finite stack space given large enough datasets or even semi-pathalogical input cases. The majority of problems can be done away with by choosing a random pivot point from the set, that way it's very unlikely (but not impossible) to achieve a pathalogical case. However, such an implementation becomes indeterministic in that there's a very small but non-zero chance that the random pivots chosen will select items from the array in relative order and lead to too many levels of recursion. To me something that blows up only very rarely, and virtually impossible to replicate, is a nightmare to debug and fix. I'd much rather put the right algorithm in there to begin with to avoid this possibility completely. There are plenty of other tricks you can implement to avoid cases like this, e.g. checking that the pivot creates partitions with at least 10% of elements in; that greatly reduces the number of possible recursions But you'd be surprised at the number of sort implementations out there in the real world which are just implementations of the basic quicksort algorithm.
- nadam 14y ago
  Thanks for your detaild answer.

by nadam 14y ago

barrkel 14y ago

Worst case is O(n). Think about it; recursing on one half after finding a pivot which turns out to be the smallest or largest (presuming you recurse on both halves). A malicious attacker may even craft data that causes this behaviour, if they know the library / variant being used.

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 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 ago
  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.

alexkus 14y ago

This is my point, the worst case of stack usage of the basic quick sort algorithm is O(n), not O(log n); O(log n) is the average case. Consider a quicksort algorithm that takes the first element in each partition and uses that as the pivot. When given sorted data it will iterate as: Notation: (left set) _pivot_ (right set) Input: 1 2 3 4 5 () _1_ (2 3 4 5) 1 is chosen as pivot, all elements in right set 1 () _2_ (3 4 5) 2 is chosen as pivot... 1 2 () _3_ (4 5) 1 2 3 () _4_ (5) Note that for each recursion we're construction the input with the aim of leaving one of the partitions empty, so that we only ever sort 1 element (the pivot) each iteration. So that's n-1 levels of recursion with n elements -> O(n) Even if you take the 'middle' (left-middle if even number) element as the pivot it's possible to construct a patalogical case:- Input: 4 2 1 3 5 () _1_ (4 2 3 5) 2 is next pivot for right partition 1 () _2_ (4 3 5) 3 is next pivot for right partition 1 2 () _3_ (4 5) 4 is next pivot as left of middle for even number of elements 1 2 3 () _4_ (5) ... Again, n-1 levels of recursion with n elements -> O(n) On the other point; I'm not saying that every implementation of quicksort out there is susceptible. I'm saying that there are quite a few implementations that are in common use that are just the basic quick sort algorithm and can be made to blow through available finite stack space given large enough datasets or even semi-pathalogical input cases. The majority of problems can be done away with by choosing a random pivot point from the set, that way it's very unlikely (but not impossible) to achieve a pathalogical case. However, such an implementation becomes indeterministic in that there's a very small but non-zero chance that the random pivots chosen will select items from the array in relative order and lead to too many levels of recursion. To me something that blows up only very rarely, and virtually impossible to replicate, is a nightmare to debug and fix. I'd much rather put the right algorithm in there to begin with to avoid this possibility completely. There are plenty of other tricks you can implement to avoid cases like this, e.g. checking that the pivot creates partitions with at least 10% of elements in; that greatly reduces the number of possible recursions But you'd be surprised at the number of sort implementations out there in the real world which are just implementations of the basic quicksort algorithm.

nadam 14y ago
Thanks for your detaild answer.