4 ms·
As someone who implemented an open source quicksort (http://www.mqseries.net/phpBB2/viewtopic.php?p=273722 http://www.mqseries.net/phpBB2/viewtopic.php?p=273722
by mqsiuser 12y ago
As someone who implemented an open source quicksort (http://www.mqseries.net/phpBB2/viewtopic.php?p=273722 http://www.mqseries.net/phpBB2/viewtopic.php?p=273722) which is used by many in production:
Now this is very interesting, but could also be prevented with a random number generator (which influences the selection of the pivot element). If this would have been exploited, people would have looked into mitigating this.
Edit: You can detect recursion-tree-degeneration (just check the depth) and react to it (pivot selection)
- sgeisenh 12y agoYeah, random pivot quicksort is n log n expected case. Its pretty easy to show that it is realistically impossible to exceed n log n for large data sets. The constants are quite high, though, due to the need to generate a random number for each element. Additionally, quicksort is just as easy to implement in parallel as mergesort and runs about as fast since it can be performed in-place.