Re: A worst case for qsort

On Wed, Aug 6, 2014 at 9:18 AM, John Cochran <j69cochran@gmail.com> wrote:
> So it seems to me that the vulnerability only exits if an attacker supplied
> comparison function is permitted. For all other cases, assuming that only
> vetted comparison functions are permitted, the selection of a random pivot
> would make an attack on qsort using specially tailored input data
> improbable.

Whether or not random pivot selection would make it more difficult for
a malicious party to generate pre-processed data that will cause very
bad performance is not all that relevant IMV, since we don't do that.
There are good practical reasons to prefer median of medians pivot
selection, which is what we actually do, and which is clearly affected
to the extent that pre-processing malicious data that causes (at
least) near worst-case performance is possible. It's possible to
predict pivot selection. As the paper says, "An adversary can make
such a quicksort go quadratic by arranging for the pivot to compare
low against almost all items not seen during pivot selection". Random
pivot selection will certainly result in more frequent lopsided
partitions without any malicious intent.

-- 
Peter Geoghegan