Worst-case performance of quickSort / getPivot

[Ivan Kazmenko]

On Sunday, 17 November 2013 at 01:48:14 UTC, Craig Dillabaugh 
wrote:
> 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.
>>
>> Let us measure quicksort performance as the number of 
>> comparisons it makes.
>>
>> Let us make some assumptions:
>> quicksort goes as
>> --(1) choose a pivot p in O(1) comparisons;
>> --(2) partition the segment into two;
>> --(3) run quicksort recursively on the two resulting segments.
>>
>> Now, (2) is effectively done by comparing every element with 
>> p, thus in Theta(n) (on the order of n) comparisons where n is 
>> the length of the current segment.
>>
>> Under these assumptions, we can construct the killer array for 
>> an arbitrary quicksort of such kind, even if we don't know how 
>> exactly the pivot is chosen (say, closed source or 
>> obfuscation), but we have the following interface to it:
>>
>> Instead of accessing the array a[], quicksort calls the 
>> function less(i,j) which tells it whether a[i]<a[j], and we 
>> control that function.
>>
>> (snip)
>
> Woah, that sounds complicated.  Not 100% sure I entirely
> understand but it seems to rely on changing the elements while
> you sort.  How would that work in real life?
>
> For example, how would this defeat the following pivoting 
> method.
>
> 1. Find the median value in the array. This can be done
> deterministically in linear time, so from a theoretical point of
> view is just as fast as picking a random element since you use
> linear time.
> 2. Use that as the pivot.

Right, this method (median of medians is an example 
implementation) will not be defeated by the above algorithm.  
There's nothing wrong in it, since it takes Theta(n) comparisons 
to choose the pivot and so violates our attack's working 
conditions.  In practice however, it means that, on an average 
case, the constant factor is very likely to be higher than for a 
quicksort vulnerable to our attack.

Ivan Kazmenko.