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