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!
