[mqsiuser]

As someone who implemented an open source quicksort (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]

Yeah, 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.