# 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

.

**Follow-Ups**:**Re: quick sort and O(nlgn) worst case bound***From:*Stephen Howe

**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

- 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):