Re: quick sort and O(nlgn) worst case bound



Stephen Howe wrote:
It also happens to be the paper under discussion.
And as Jon Harrop has stated,
the paper does not apply to all quicksorts.

Yes does the paper apply to quicksorts where the pivot selection is O(1) ?
If the pivot selection is O(N) you can gurantee to get the median every time.

I think I am saying that all quicksorts will have at least 1 worst case if the pivot selection is O(1)

Um, did you mean what you just said? Surely *all* algorithms have at least 1 worst case?

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
Sig line vacant - apply within
.