> -----Original Message-----
> From: Steve Wampler [mailto:swampler@noao.edu] 
> Sent: Monday, April 07, 2003 1:58 PM
> To: Dann Corbit
> Cc: Jason M. Felice; Postgres-hackers
> Subject: Re: [HACKERS] No merge sort?
> On Mon, 2003-04-07 at 13:39, Dann Corbit wrote:
> > > -----Original Message-----
> > > From: Jason M. Felice [mailto:jfelice@cronosys.com]
> > > Sent: Monday, April 07, 2003 1:10 PM
> > > To: pgsql-hackers@postgresql.org
> > > Subject: Re: [HACKERS] No merge sort?
> > > 
> > > 
> > > On Mon, Apr 07, 2003 at 03:36:10PM -0400, Greg Stark wrote:
> > > > "Ron Peacetree" <rjpeace@earthlink.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...

An array holding all possible outcomes is an implementation of this
algorithm.
Quite frankly, it's rather silly (as it is intended to be).


Mon, 7 Apr 2003 14:02:30 -0700
"Dann Corbit" <DCorbit@connx.com>
Re: No merge sort?