3 ms·
Very many implementations of quicksort are vulnerable to inputs that trigger quadratic runtime because of improper selection of the pivot element.
by jakobegger 9y ago
Very many implementations of quicksort are vulnerable to inputs that trigger quadratic runtime because of improper selection of the pivot element.
- cesarb 9y agoLess well-known, not only is the selection of the pivot element important, but also the selection of which side you use recursion: "[...] it always recurses on the first sub-partition, and iterates on the second sub-partition; but instead, it should always recurse on the smaller sub-partition, and iterate on the larger sub-partition [...] our attack constructs an input array of N elements that causes qsort() to recurse N/4 times." https://www.qualys.com/2017/06/19/stack-clash/stack-clash.txt https://www.qualys.com/2017/06/19/stack-clash/stack-clash.tx... That's from last month.