Re: No merge sort?

On Mon, 2003-04-07 at 13:39, Dann Corbit wrote:
> > -----Original Message-----
> > From: Jason M. Felice [mailto:jfelice(at)cronosys(dot)com]
> > Sent: Monday, April 07, 2003 1:10 PM
> > To: pgsql-hackers(at)postgresql(dot)org
> > Subject: Re: [HACKERS] No merge sort?
> >
> >
> > On Mon, Apr 07, 2003 at 03:36:10PM -0400, Greg Stark wrote:
> > > "Ron Peacetree" <rjpeace(at)earthlink(dot)net> writes:
> > >
> > > > AFAIK, there are only 3 general purpose internal sorting
> > techniques
> > > > that have O(n) behavior:
> > >
> > > Strictly speaking there are no sorting algorithms that have
> > worst-case
> > > time behaviour better than O(nlog(n)). Period.
> > >
> >
> > Not true.
> >
> http://www.elsewhere.org/jargon/html/entry/bogo-sort.html
>
> He said "better than" not "worse than".
>
> For comparison based sorting it is _provably_ true that you cannot sort
> faster than log(n!) which is O(n*(log(n))).

You didn't read far enough. The 2nd form of the bogo sort is O(1),
at least in *one* universe...

--
Steve Wampler <swampler(at)noao(dot)edu>
National Solar Observatory