Worst-case performance of quickSort / getPivot

[Chris Cain]

On Sunday, 17 November 2013 at 01:39:43 UTC, Chris Cain wrote:
> (if a quicksort were designed wise to this sort of trick, but 
> most, including D's quicksort, would actually shuffle 
> everything around)

Actually, not everything. It'd swap the pivot and the last 
element (4 and 7 for the first iteration) and then swap it back 
after it figures out the two partitions are good. There was a 
case where it ended up swapping everything around unnecessarily, 
but it wasn't this case... But I digress, the point remains that 
it would be slower than Timsort despite having a good pivot.