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