Quicksort partitioning normally takes O(N) time, but it can be in some sense perfectly parallelized once you have the pivot.
So if you have to have unique keys, each comparison is going to take O(log N) time instead of O(1) time, so the overall algorithm takes O(N log² N) time. On the other hand, this is somewhat of a theoretical consideration if your keys are more than about 4–6 bytes long in the first place, since it's not very practical to store 2⁴⁸ records. But 2⁴⁸ is a long way from ∞, and if you're going to fudge by treating the theoretical factor of log N as constant, you might as well claim that Quicksort is O(N) with a constant of, say, less than 100 comparisons per key.
I don't know anything about analyzing parallel quicksort, but maybe this key-comparison-time factor explains it? Because it seems like key comparisons would pretty much have to be serialized on Quicksort's critical path, no?
Example of the superscript notation meaning squared: http://www.springerlink.com/content/7n7219tcyxr81gxc/
http://www.cs.cmu.edu/~scandal/nesl/alg-sequence.html#quicks...
Or do I misunderstand something?