Re: quick sort and O(nlgn) worst case bound
 From: Richard Heathfield <rjh@xxxxxxxxxxxxxxx>
 Date: Fri, 29 Jan 2010 16:10:02 +0000
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
.
 FollowUps:
 Re: quick sort and O(nlgn) worst case bound
 From: Stephen Howe
 Re: quick sort and O(nlgn) worst case bound
 References:
 Re: quick sort and O(nlgn) worst case bound
 From: Daniel Pitts
 Re: quick sort and O(nlgn) worst case bound
 From: Jon Harrop
 Re: quick sort and O(nlgn) worst case bound
 From: Ben Bacarisse
 Re: quick sort and O(nlgn) worst case bound
 From: Willem
 Re: quick sort and O(nlgn) worst case bound
 From: Ben Bacarisse
 Re: quick sort and O(nlgn) worst case bound
 From: Jon Harrop
 Re: quick sort and O(nlgn) worst case bound
 From: Alf P. Steinbach
 Re: quick sort and O(nlgn) worst case bound
 From: Moi
 Re: quick sort and O(nlgn) worst case bound
 From: pete
 Re: quick sort and O(nlgn) worst case bound
 From: Stephen Howe
 Re: quick sort and O(nlgn) worst case bound
 Prev by Date: Re: Is there a newsgroup for algorithmic research?
 Next by Date: Re: quick sort and O(nlgn) worst case bound
 Previous by thread: Re: quick sort and O(nlgn) worst case bound
 Next by thread: Re: quick sort and O(nlgn) worst case bound
 Index(es):
Relevant Pages
