Worst-case performance of quickSort / getPivot

[Andrei Alexandrescu]

On 11/16/13 5:39 PM, Chris Cain wrote:
> 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).

I keep on thinking of a sort with delayed pivot selection that starts 
scanning the array from left and right and only stops when it figures 
it's unpartitioned. At that point it proceeds with pivot selection, but 
if the array is already sorted there's no need to partition the left and 
right portions that were already explored. Essentially the pivot 
selection would be preceded by a sampling of the left and right of the 
array.

> 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!

Yah, already sorted data is ideal for Timsort.


Andrei