Worst-case performance of quickSort / getPivot

[Chris Cain]

On Sunday, 17 November 2013 at 01:07:20 UTC, Ivan Kazmenko wrote:
> Regarding an ideal pivot choice for quicksort, I'd like to 
> emphasize that it is simply non-existent.  Here's why.

Oh, of course. I did that in an algorithms class taught by a 
Professor who is into Cryptography. I agree that essentially 
there is no way to pick pivots that avoid worst case performance 
when an attacker is involved. When I mentioned "ideal pivot" I 
mean an actual good one on a sorted sequence

Given [1,2,3,4,5,6,7]
Picking the best pivot, 4 would result in scanning the entire 
array to assure that it is partitioned appropriately around the 4 
(if a quicksort were designed wise to this sort of trick, but 
most, including D's quicksort, would actually shuffle everything 
around). By that point, Timsort is already done and drinking the 
victory champagne. And the quicksort still has to recur on the 
subsequences to sort them as well!