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
